Adventures of Dunno and His Friends

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

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

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

Examples