Bruce developed a new hopscotch. In the game, a single row of ~N~ squares is drawn along the ground. The squares are numbered from ~0~ to ~N-1~. Each square ~i~ has a power value ~K_i~, which enables Bruce to directly hop to the square ~i+K_i~ (Bruce can only hop to ~i+K_i~, but not any other square). If the square ~i+K_i~ is beyond the ~N~ squares (~i+K_i \ge N~), Bruce finishes the game. To make the game more interesting, Bruce can dynamically change the power value of square ~i~. At the same time, Bruce wants to know the number of hops he requires if he starts from the square ~i~. Could you please write a program to help Bruce?

Input Specification

The first line of input will contain one integer, ~N~ ~(1 \le N \le 200\,000)~, the number of squares. Note, squares are numbered from ~0~ to ~N-1~.

The second line of input will contain ~N~ positive integers, ~K_i~ ~(1 \le K_i \le 10^7)~, which is the initial power value of the square ~i~.

The third line of input will contain ~Q~ ~(1 \le Q \le 100\,000)~, the number of operations Bruce will take.

Each of the next ~Q~ lines will be one of the following operations:

1. ~1\ x~: Query the number of hops required if Bruce starts from the square ~x~ ~(0 \le x \le N-1)~.
2. ~2\ x\ v~: Change the power value of the square ~x~ to ~v~ ~(0 \le x \le N-1, 1 \le v \le 10^7)~.

Output Specification

For any operation ~1~, output one single integer on a line.

Sample Input

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

Sample Output

2
3

Explanation for Sample Output

There are ~4~ squares in the game, and the initial power values are ~\{1, 2, 1, 1\}~. If Bruce starts from square ~1~, Bruce will hop to square ~1+2=3~. Square ~3~ has the power of ~1~. So, Bruce will hop to square ~3+1=4~, and finishes the game with ~2~ hops.

In the second operation, Bruce changes square ~1~'s power to ~1~. The new power values are ~\{1, 1, 1, 1\}~.

If Bruce starts from square ~1~, he will hop from square ~1~ to square ~2~, from square ~2~ to square ~3~, from square ~3~ to square ~4~, and finishes the game with ~3~ hops.