HopScotch

View as PDF

Submit solution

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

The first line of input will contain one integer, N (1 \le N \le 200\,000), the number of squares. Note, square is 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

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

Sample Case Explanation

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 change the 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.


Comments


  • -8
    Beautiful_Times  commented on Nov. 9, 2017, 8:25 p.m.

    This comment is hidden due to too much negative feedback. Click here to view it.