Description

One day, Lostmonkey invented a super elastic device. To show off in front of his sheep friends, he invited a little sheep to play a game.

At the start of the game, Lostmonkey places $n$ devices along a straight line on the ground. Each device has an initial elasticity coefficient $k_i$. When the sheep reaches the $i$-th device, it will bounce forward $k_i$ steps, reaching the $(i + k_i)$-th device. If the $(i + k_i)$-th device does not exist, the sheep will be launched away.

The sheep wants to know, starting from the $i$-th device, after how many bounces it will be launched away. To make the game more interesting, Lostmonkey may modify the elasticity coefficient of any device, and the coefficients are positive integers at all times.

Input Format

The first line contains an integer $n$, indicating there are $n$ devices on the ground, numbered from $0 \sim n-1$.

The next line contains $n$ positive integers, which are the initial elasticity coefficients of the $n$ devices in order.

The third line contains a positive integer $m$, the number of operations. Each of the next $m$ lines contains at least two integers $i, j$.

• If $i = 1$, you should output after how many bounces the sheep starting from device $j$ will be launched away.
• If $i = 2$, there will be one more positive integer $k$, meaning the coefficient of device $j$ is updated to $k$.

Output Format

For each operation with $i = 1$, output one line containing a single integer representing the answer.

4
1 2 1 1
3
1 1
2 1 1
1 1

2
3

Hint

Constraints
For $20\%$ of the testdata, $1 \le n, m \le 10^4$.
For $100\%$ of the testdata, $1 \le n \le 2 \times 10^5$, $1 \le m \le 10^5$.

Translated by ChatGPT 5