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