{"code":"hoangarrayinc","name":"Tăng mảng","description":"Cho mảng số nguyên $n$ phần tử $a_1, a_2, ..., a_n$, bảng sẽ được biến đổi sau mỗi thời điểm như sau: với mỗi số $a_i$ ta sẽ đếm xem có bao nhiêu **giá trị khác nhau** trong mảng $a$ mà giá trị lớn hơn $a_i$ và tăng $a_i$ lên đúng bằng số lượng giá trị khác nhau đó. Tại một thời điểm tất cả các phần tử đều biến đổi như trên.\r\n\r\nHãy trả lời các truy vấn trong 3 loại sau:\r\n- $1\\ k$: đến thời điểm $k$ thì có bao nhiêu giá trị khác nhau trong mảng\r\n- $2\\ k$: tổng số giá trị tăng lên của tất cả các phẩn tử đến thời điểm $k$ là bao nhiêu\r\n- $3\\ k\\ i$: giá trị của phần tử $a_i$ đến thời điểm $k$ bằng bao nhiêu\r\n\r\n

Input

\r\n\r\n- Dòng đầu chứa số $n, q$ ($1\\le n, q\\le 3\\cdot 10^5$)\r\n\r\n- Dòng thứ hai chứa $n$ số $a_i$ ($1\\le a_i \\le 10^{12}$)\r\n\r\n- $q$ dòng tiếp theo mỗi dòng mô tả một trong ba truy vấn trên ($0\\le k\\le 10^{12}, 1\\le i\\le n$)\r\n\r\n

Output

\r\n\r\n- Ghi ra kết quả trên $q$ dòng.\r\n\r\n

Example

\r\n\r\n!!! question \"Test 1\"\r\n\r\n ???+ \"Input\"\r\n\r\n ```sample\r\n 6 6\r\n 5 4 4 2 2 2\r\n 1 0\r\n 1 1\r\n 1 2\r\n 2 1\r\n 2 2\r\n 3 1 5\r\n ```\r\n\r\n ???+ success \"Output\"\r\n\r\n ```sample\r\n 3\r\n 2\r\n 1\r\n 8\r\n 11\r\n 4\r\n ```\r\n\r\n!!! question \"Test 2\"\r\n\r\n ???+ \"Input\"\r\n\r\n ```sample\r\n 5 4\r\n 0 3 5 4 2\r\n 1 0\r\n 1 1\r\n 2 1\r\n 3 1 1\r\n ```\r\n\r\n ???+ success \"Output\"\r\n\r\n ```sample\r\n 5\r\n 2\r\n 10\r\n 4\r\n ```","points":100.0,"partial":true,"time_limit":2.0,"memory_limit":530000,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}