After our alien visitors landed, the scientific community is in uproar over the fascinating trees that grew in the wake of our otherworldly visitors. These trees have a trunk diameter of zero and have no leaves or roots. How photosythesis occurs in these trees if it occurs at all is up to speculation. In fact, these trees can be better modeled as mathematical rays. Your job, as the newest hire of the Logging Company, is to produce an image of the forest viewed from above if the trees were light rays. Just kidding. We don't do that to our new hires.

Ahem. Your actual task today is to find the number of trees between tree number ~i~ ~{(0 \le i < N)}~ and tree number ~j~ ~{(i \le j < N)}~ that also have a height greater than or equal to ~a~ and less than or equal to ~b~, given the heights of the ~N~ trees. However, the trees grow occasionally and your answers must be adjusted to account for growth. Unsurprisingly, it's even possible for a tree to ungrow.

Input Specification

On the first line you will find ~N~ ~{(1 \le N \le 2^{13})}~, the number of trees.

On the second line you will find ~N~ natural numbers ~h_i~ ~{(0 \le h_i < N)}~ separated by spaces.

On the third line you will find ~Q~ ~{(1 \le Q \le 2^{21})}~, the number of queries.

The queries can be one of two types:

• ~1~ ~i~ ~j~ ~a~ ~b~, which is a question of the form "how many trees with index ~k~ ~{(0 \le i \le k \le j < N)}~ have height ~h~ ~{(a \le h \le b)}~?"
• ~2~ ~i~ ~h~, which indicates that the tree at index ~i~ ~(0 \le i < N)~ has grown (or ungrown) to a height of ~h~ ~{(0 \le h < N)}~

The subsequent ~Q~ lines each contain one query of the form described above.

Output Specification

Output one natural number per line to answer each of the queries.

Subtasks

Subtask 1 [2p]

~{N \le 2^{8}}~

~{Q \le 2^{10}}~

Subtask 2 [3p]

~{N \le 2^{11}}~

Subtask 3 [10p]

No further restrictions

Sample Input 1

10
3 3 9 4 7 6 6 6 0 3
10
1 2 4 4 5
1 4 8 2 3
2 5 3
1 4 7 0 6
1 1 4 1 2
1 0 2 0 2
1 0 9 0 4
2 5 6
1 0 7 0 1
2 3 3

Sample Output 1

1
0
3
0
0
6
0

Sample Input 2

4
2 2 0 0
16
1 0 3 0 1
2 0 1
1 0 3 0 1
1 1 2 0 1
1 0 3 0 2
2 0 0
2 2 2
2 1 0
1 1 3 2 2
2 1 3
1 1 2 0 3
2 0 2
1 0 1 1 2
2 3 3
1 1 3 1 1
2 3 2

Sample Output 2

2
3
1
4
1
2
1
0