## CCO Preparation Test 6 P3 - HopScotch

View as PDF

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

Author:
Problem type
Allowed languages
C, 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 Specification

The first line of input will contain one integer,  , the number of squares. Note, squares are 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 Specification

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

#### Explanation for Sample Output

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