You are given a 1-indexed array X, consisting of N integers, and a set of Q queries. There are two kinds of queries:

1. 0 a b c
   Here you are required to return the number of elements with indices in [a,b]
   greater than or equal to c
2. 1 a b
   Here you are required to change the a^th element of array to b.

Input Format:

First line contains N, the number of elements in the array X. The next line contains N space separated integers representing the elements of X. The third line of input contains a single integer, Q, the number of queries. The next Q lines of input each contain queries of two kinds as described above.

Output Format:

Q lines with the ith line contains the answer for the i^th query

Constraints:

1 ≤ N ≤ 5*10^5
1 ≤ Q ≤ 10^5
1 ≤ X[i] ≤ 10^9
1 ≤ a ≤ b ≤ N for query type 0
1 ≤ a ≤ 10^5, 1 < b ≤ 10^9 for query type 1
1 ≤ c ≤ 10^9

Example

Sample Input:
5
1 2 3 4 5
3
0 1 5 10
1 2 20
0 1 3 10
Sample Output:
0
1

Problem Setter: Pulkit Goel and Vidit Gupta