[HNOI2010]弹飞绵羊

题目描述

某天,Lostmonkey 发明了一种超级弹力装置,为了在他的绵羊朋友面前显摆,他邀请小绵羊一起玩个游戏。 游戏一开始,Lostmonkey 在地上沿着一条直线摆上 $n$ 个装置,每个装置设定初始弹力系数 $k_i$,当绵羊达到第 $i$ 个装置时,它会往后弹 $k_i$ 步,达到第 $i+k_i$ 个装置,若不存在第 $i+k_i$ 个装置,则绵羊被弹飞。 绵羊想知道当它从第 $i$ 个装置起步时,被弹几次后会被弹飞。为了使得游戏更有趣,Lostmonkey 可以修改某个弹力装置的弹力系数,任何时候弹力系数均为正整数。

输入输出格式

输入格式


第一行包含一个整数 $n$,表示地上有 $n$ 个装置,装置的编号从 $0 \sim n-1$。 接下来一行有 $n$ 个正整数,依次为那 $n$ 个装置的初始弹力系数。 第三行有一个正整数 $m$,表示操作次数。接下来 $m$ 行每行至少有两个数 $i,j$。 - 若 $i=1$,你要输出从 $j$ 出发被弹几次后被弹飞 - 若 $i=2$,则还会再输入一个正整数 $k$,表示第 $j$ 个弹力装置的系数被修改成 $k$。

输出格式


对于每个 $i=1$ 的操作,输出一行一个整数表示答案。

输入输出样例

输入样例 #1

4
1 2 1 1
3
1 1
2 1 1
1 1

输出样例 #1

2
3

说明

【数据范围】 对于 $20\%$ 的数据,$1 \le n,m \le 10^4$; 对于 $100\%$ 的数据,$1\le n \le 2\times 10^5$,$1\le m \le 10^5$。