Sequence and Queries 1.5

Time limit1.5sMemory limit512 MB

Summary
Maintain an array under point updates and answer range queries counting how many elements in a subarray exceed k.
Level

Medium7 of 10

Topics
Segment tree, Sorting, Binary search, Array
Solved
No attempts yet

Problem

A sequence A1, A2, ..., AN of length N is given. Write a program that performs the following queries.

  • 1 i v: set Ai to v. (1 ≤ i ≤ N, 1 ≤ v ≤ 104)
  • 2 i j k: print the number of elements greater than k in the subsequence Ai, Ai+1, ..., Aj. (1 ≤ i ≤ j ≤ N, 1 ≤ k ≤ 104)

Indices of the sequence start at 1.

Input

The first line contains the size of the sequence N (1 ≤ N ≤ 100,000).

The second line contains A1, A2, ..., AN. (1 ≤ Ai ≤ 104)

The third line contains the number of queries M (2 ≤ M ≤ 200,000).

The next M lines contain one query each. At least one query of type 2 is given.

Output

For each type 2 query, print the answer on its own line in order.

Examples1

  1. Example 1

    Input
    5
5 1 2 3 4
9
2 2 4 1
2 4 4 4
2 1 5 2
1 2 5
2 2 4 1
1 4 5
2 4 4 4
1 5 1
2 1 5 2
    Expected output
    2
0
3
3
1
3