Under construction

Still being built. Things may change

Sequence and Queries 18

Time limit2sMemory limit512 MB

Summary
Maintain an array under point updates and answer range queries counting elements greater than k.
Level

Hard8 of 10

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

Problem

You are given a sequence A1,A2,…,ANA_1, A_2, \ldots, A_N of length NN. Write a program that processes the following queries.

  • 1 i j k: print the number of elements among Ai,Ai+1,…,AjA_i, A_{i+1}, \ldots, A_j that are greater than kk.
  • 2 i k: change AiA_i to kk.

The sequence is indexed from 1.

Input

The first line contains the length of the sequence NN (1≤N≤100,0001 \le N \le 100{,}000).

The second line contains A1,A2,…,ANA_1, A_2, \ldots, A_N (1≤Ai≤1091 \le A_i \le 10^9).

The third line contains the number of queries MM (1≤M≤100,0001 \le M \le 100{,}000).

Each of the next MM lines contains one query in the format described above (1≤i≤j≤N1 \le i \le j \le N, 1≤k≤1091 \le k \le 10^9).

Output

For each query of type 1, print the answer on its own line.

Examples1

  1. Example 1

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