Giải bài trực tuyến

Given a sequence of n numbers a₁, a₂, ..., a_n and a number of k-queries. Besides, you are also given some modify operations.

A modify operation is a pair (i, v) which means a_i should be set to be v.

A k-query is a triple (i, j, k). For each k-query (i, j, k), you have to return the number of elements greater than k in the subsequence a_i, a_i+1, ..., a_j.

Input

• Line 1: n (1 ≤ n ≤ 30000).
• Line 2: n numbers a₁, a₂, ..., a_n (1 ≤ a_i ≤ 10⁴) representing the initial sequence.
• Line 3: q (1 ≤ q ≤ 200000), the number of operations.
• In the next q lines, the first number of each line contains a flag value which is either 0 or 1. A flag 0 follows by 2 numbers i and v (1 ≤ i ≤ n, 1 ≤ v ≤ 10⁴) representing a modify operation. A flag 1 follows by 3 numbers i, j and k (1 ≤ i ≤ j ≤ n, 1 ≤ k ≤ 10⁴) representing a k-query.

Output

• For each k-query (i, j, k), print the number of elements greater than k in the subsequence a_i, a_i+1, ..., a_j in a single line.

Example

Input
5
5 1 2 3 4
6
1 2 4 1
0 4 10
1 4 4 4
0 3 1
0 1 2
1 1 5 2 

Output
2
1
2