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 photosynthesis 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 and tree number that also have a height greater than or equal to and less than or equal to , given the heights of the 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 , the number of trees.

On the second line, you will find natural numbers separated by spaces.

On the third line, you will find , the number of queries.

The queries can be one of two types:

- , which is a question of the form "how many trees with index have height ?"
- , which indicates that the tree at index has grown (or ungrown) to a height of .

The subsequent 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 [2/15]

##### Subtask 2 [3/15]

##### Subtask 3 [10/15]

No additional constraints.

#### 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
```

## Comments

Apparently brute force still passes. Maybe update the constraints again?

Constraints Updated to Fail Brute Force Solutionshas been raised from to and has been raised from to . In addition, the time limit is raised to 10 seconds from 4 seconds and the memory limit to 512M from 128M. Sorry for the inconvenience.

I still pass it with brute force in C++11 after enabling optimization using preprocessing command.

(However, I got Compile Error in CCC contest after adding

#pragma GCC optimize("Ofast")in the beginning of my source code.)Thanks for the tip, now I have the fastest submission using brute force.

Except d still passed