Dynamic array
To implement a data structure that represents a dynamic array, you need to support the following operations:
Assign the value p to the element at position u.
Insert the number p immediately after position u (before position u+1, if it exists).
Determine how many numbers not exceeding p are located between positions u and v, inclusive.
The elements in the array are indexed starting from one.
Input
The first line contains two natural numbers n and m - the initial number of elements in the array and the number of operations, respectively (1 ≤ n ≤ 200000, 1 ≤ m ≤ 200000). The second line contains n integers a_1, a_2, ..., a_n - the elements of the initial array (0 ≤ a_i ≤ 10^6). The following m lines describe the operations in one of the following formats:
1 u p (u ≥ 1, u does not exceed the current size of the array, 0 ≤ p ≤ 10^6),
2 u p (u ≥ 0, u does not exceed the current size of the array, 0 ≤ p ≤ 10^6),
or
3 u v p (1 ≤ u ≤ v, v does not exceed the current size of the array, 0 ≤ p ≤ 10^6).
Output
The output should contain the results of the queries, each on a separate line.