eolymp
bolt
Try our new interface for solving problems
Problems

Adventures of Dunno and His Friends

Adventures of Dunno and His Friends

Time limit 1 second
Memory limit 128 MiB

We all remember the story how Dunno and his friends traveled in a balloon. But not everyone knows that not all the men climbed into a ball, because it had a limited capacity.

In this problem you need to know how many men departed to travel. It is known that the balloon boarding is not optimal: men go into the balloon in the same sequence as they stand in the line, when for some of them there is not enough space in the balloon, he and all the rest in the line turn around and go home.

Input data

The first line contains the number of men n~(1 \le n \le 10^6) in the flower city. The second line contains the weights of the men in the order of their boarding. All weights are positive integers not greater than 10^9. Then the number of queries m~(1 \le m \le 10^5) is given. Each query is given in one line. The first number t in a line is the query type.

  • If t = 1, then given one integer v~(1 \le v \le 10^9) — the balloon load capacity.

  • If t = 2, then given two integers x~(1 \le x \le n) and y~(1 \le y \le 10^9) — the weight of a person at position x becomes y.

Output data

For each query with the number one print in a separate line the number of men that can be boarded the balloon.

Examples

Input example #1
5
1 2 3 4 5
5
1 7
1 3
2 1 5
1 7
1 3
Output example #1
3
2
2
0
Author Alexandr Burkov
Source Distance Summer Computer School - Summer 2013