Insertion Sort Homework Query

Insertion sort is a very common and simple sorting algorithm. In class, teacher H explained the insertion sort algorithm. Suppose there is an array a of length \(n\) (indexed from 1) storing non‐negative integers. By assuming that comparing two elements takes \(\mathcal O(1)\) time, insertion sort can sort the array in \(\mathcal O(n^2)\) time. For example, one simple implementation based on the following pseudocode (and its corresponding C/C++ and Pascal examples) is given:

for i = 1 to n do
    for j = i downto 2 do
        if a[j] < a[j-1] then
            swap( a[j], a[j-1] )

To help student Xiao Z understand insertion sort better, teacher H has assigned the following homework. You are given an array a of length \(n\) (indexed from 1). You need to support \(Q\) operations on this array. There are two types of operations:

• 1 x v: Modify the value of the \(x\)-th element \(a_x\) to \(v\). It is guaranteed that \(1 \le x \le n\) and \(1 \le v \le 10^9\). Note: This operation permanently changes the array and will affect later operations.
• 2 x: Consider sorting the current array a with the above insertion sort algorithm (i.e. stable sort by value). You need to determine the new position of the original \(a_x\) in the sorted array. It is guaranteed that \(1 \le x \le n\). Note: This query does not change the array, and the sorted array is not retained.

Since teacher H prefers few modifications, it is guaranteed that the number of type 1 operations does not exceed 5000.

For each operation of the second type, output the new position (1-indexed) of the originally chosen element \(a_x\) in the sorted array.
Hint: Since the insertion sort used here is stable, the new position of \(a_x\) is equal to the number of elements with a value less than \(a_x\) plus the number of elements with a value equal to \(a_x\) that originally come before \(x\), plus one.

inputFormat

The first line contains two integers \(n\) and \(Q\) separated by a space, representing the length of the array and the number of operations respectively.

The second line contains \(n\) non-negative integers \(a_1, a_2, \ldots, a_n\), separated by spaces.

Each of the following \(Q\) lines contains an operation in one of the following formats:

• 1 x v: Set \(a_x = v\).
• 2 x: Query the new position of the original \(a_x\) after sorting.

outputFormat

For each query operation (type 2), output one integer on a separate line representing the new position of the queried element in the sorted array.

sample

5 5
4 2 2 5 1
2 1
1 2 6
2 2
1 5 3
2 5

4
5
2