235. 彈跳ㄠㄨ

0 Judge

Code: 0


彈跳ㄠㄨ

某天,卦長發明了一種超級彈力裝置,他邀請ㄠㄨ一起玩個遊戲。遊戲一開始,卦長在地上沿著一條直線擺上$N$個裝置,編號依序為$0 \sim N-1$,每個裝置設定初始彈力係數$K_i$,當ㄠㄨ達到第$i$個裝置時,它會往後彈$K_i$步,達到第$i+K_i$個裝置,若不存在第$i+K_i$個裝置,則ㄠㄨ會撞到地上和阿爾塔納進行融合。

ㄠㄨ想知道當它從第$i$個裝置起步時,被彈幾次後會撞到地上。為了使得遊戲更有趣,卦長可以修改某個彈力裝置的彈力係數,任何時候彈力係數均為正整數。

輸入說明

第一行包含一個整數$N$,表示地上有$N$個裝置,裝置的編號依序為$0 \sim N-1$,接下來一行有$N$個正整數,依次為那$N$個裝置的初始彈力係數。第三行有一個正整數$M$,接下來$M$行每行各有一個操作,操作有兩種:

  1. 1 x:
    表示ㄠㄨ想知道從第$x$個裝置起步被彈幾次會撞到地上
  2. 2 x c:
    表示卦長將$K_x$改為c

保證所有$1 \leq K_i,c \leq N$,$0 \leq x \leq N-1$

  • 對於其中 20% 的測試資料,$1 \leq N,M \leq 10000$。
  • 對於其中 100% 的測試資料,$1 \leq n \leq 200000$、$0 \leq m \leq 100000$。

輸出說明

對於第一種操作,請輸出ㄠㄨ從第$x$個裝置起步被彈幾次會撞到地上。

範例輸入

範例輸出


Judge Setting

run-time limit: 450 ms
memory limit: 512000 byte
測資數量: 0