## HopScotch

View as PDF

Points: 20 (partial)
Time limit: 1.0s
Memory limit: 256M

Author:
Problem type
Allowed languages
C++, Java, Pascal

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?

#### Input

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

1.  : Query the number of hops required if Bruce starts from the square ( ).
2.   : Change the power value of the square to ( , ).

#### Output

For any operation , 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

#### 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.