Bruce developed a new hopscotch. In the game, a single row of squares is drawn along the ground. The squares are numbered from to . Each square has a power value , which enables Bruce to directly hop to the square (Bruce can only hop to , but not any other square). If the square is beyond the squares (), Bruce finishes the game. To make the game more interesting, Bruce can dynamically change the power value of square . At the same time, Bruce wants to know the number of hops he requires if he starts from the square . Could you please write a program to help Bruce?
The first line of input will contain one integer, (), the number of squares. Note, square is numbered from to .
The second line of input will contain positive integers, (), which is the initial power value of the square .
The third line of input will contain (), the number of operations Bruce will take.
Each of the next lines will be one of the following operations
- : Query the number of hops required if Bruce starts from the square ().
- : Change the power value of the square to (, ).
For any operation , output one single integer on a line.
4 1 2 1 1 3 1 1 2 1 1 1 1
Sample Case Explanation
There are squares in the game, and the initial power values are . If Bruce starts from square , Bruce will hop to square . Square has the power of . So, Bruce will hop to square , and finishes the game with hops.
In the second operation, Bruce change the square 's power to . The new power values are .
If Bruce starts from square , he will hop from square to square , from square to square , from square to square , and finishes the game with hops.