Problem Description

Insertion sort is a very common and simple sorting algorithm. Little Z is a freshman in college, and today in class, Teacher H has just explained the insertion sort algorithm.

Assume that comparing two elements takes $\mathcal O(1)$ time. Then insertion sort can sort an array of length $n$ in $\mathcal O(n^2)$ time. Suppose these $n$ numbers are stored in $a_1, a_2, \ldots, a_n$. The following pseudocode gives one of the simplest implementations of insertion sort:

The following is sample code in C/C++:

for (int i = 1; i <= n; i++)
	for (int j = i; j >= 2; j--)
		if (a[j] < a[j-1]) {
			int t = a[j-1];
			a[j-1] = a[j];
			a[j] = t;
		}

The following is sample code in Pascal:

for i:=1 to n do
	for j:=i downto 2 do
		if a[j]<a[j-1] then
			begin
				t:=a[i];
				a[i]:=a[j];
				a[j]:=t;
			end;

To help Little Z better understand insertion sort, Teacher H left the following homework:

Teacher H gives an array $a$ of length $n$, with indices starting from $1$, and all elements are non-negative integers. Little Z needs to support $Q$ operations on array $a$. There are two types of operations, with parameters as follows:

$1~x~v$: This is the first type of operation. It modifies the value of the $x$-th element of $a$, i.e. $a_x$, to $v$. It is guaranteed that $1 \le x \le n$, $1 \le v \le 10^9$. Note that this operation changes the array elements. The modified array will be kept and will affect subsequent operations.

$2~x$: This is the second type of operation. Suppose Teacher H sorts array $a$ according to the pseudocode above. You need to tell Teacher H the position of the original $x$-th element of $a$, i.e. $a_x$, in the new array after sorting. It is guaranteed that $1 \le x \le n$. Note that this operation does not change the array elements. The sorted array will not be kept and will not affect subsequent operations.

Teacher H does not like too many modifications, so he guarantees that the number of type $1$ operations does not exceed $5000$.

Little Z has not studied competitive programming, so he cannot solve this problem. He comes to you for help.

Input Format

The first line contains two positive integers $n, Q$, representing the array length and the number of operations.

The second line contains $n$ space-separated non-negative integers, where the $i$-th non-negative integer represents $a_i$.

The next $Q$ lines each contain $2 \sim 3$ positive integers, representing one operation. The operation format is described in Description.

Output Format

For each query of type $2$, output one line with one positive integer as the answer.

3 4
3 2 1
2 3
1 3 2
2 2
2 3

1
1
2

Hint

Sample Explanation #1

Before the modification operation, suppose Teacher H performs one insertion sort. Then the positions of the three elements in the original sequence after sorting are $3, 2, 1$, respectively.

After the modification operation, suppose Teacher H performs one insertion sort. Then the positions of the three elements in the original sequence after sorting are $3, 1, 2$, respectively.

Note that although $a_2 = a_3$ at this time, we cannot treat them as the same element.

Sample #2

See the attached files sort/sort2.in and sort/sort2.ans.

The Constraints for this test point are the same as test points $1 \sim 2$.

Sample #3

See the attached files sort/sort3.in and sort/sort3.ans.

The Constraints for this test point are the same as test points $3 \sim 7$.

Sample #4

See the attached files sort/sort4.in and sort/sort4.ans.

The Constraints for this test point are the same as test points $12 \sim 14$.

Constraints

For all testdata, $1 \le n \le 8000$, $1 \le Q \le 2 \times {10}^5$, $1 \le x \le n$, $1 \le v,a_i \le 10^9$.

For all testdata, among all $Q$ operations, there are at most $5000$ operations of type $1$.

The additional constraints and scores for each test point are shown in the table below.

Translated by ChatGPT 5