Description

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

Input

第一行包含一个整数n，表示地上有n个装置，装置的编号从0到n-1。

接下来一行有n个正整数，依次为那n个装置的初始弹力系数。

第三行有一个正整数m，

接下来m行每行至少有两个数i、j，若i=1，你要输出从j出发被弹几次后被弹飞，若i=2则还会再输入一个正整数k，表示第j个弹力装置的系数被修改成k。

Output

对于每个i=1的情况，你都要输出一个需要的步数，占一行。

Sample Input

4

1 2 1 1

3

1 1

2 1 1

1 1

Sample Output

2

3

Solution

比较简单的分块

对每个分块维护两个值：跳出这个块需要的次数、跳出这个块后所在位置

那么查询和修改就很简单了~

Code

//By Menteur_Hxy#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #define F(i,a,b) for(register int i=(a);i<=(b);i++)#define R(i,a,b) for(register int i=(b);i>=(a);i--)using namespace std;int rd() {    int x=0,f=1; char c=getchar();    while(!isdigit(c)) {if(c=='-')f=-f; c=getchar();}    while(isdigit(c)) x=(x<<1)+(x<<3)+c-48,c=getchar();    return x*f;}const int N=200010;int n,q,blo;int da[N],cnt[N],to[N],bl[N],l[N],r[N];void init() {    R(i,1,n) {        if(bl[i]!=bl[i+1]) r[bl[i]]=i;        if(bl[i]!=bl[i-1]) l[bl[i]]=i;        if(i+da[i]>n) cnt[i]=1,to[i]=n+1;        else if(i+da[i]>r[bl[i]]) cnt[i]=1,to[i]=i+da[i];        else cnt[i]=cnt[i+da[i]]+1,to[i]=to[i+da[i]];    }}void query(int x) {    int ans=0;    while(x!=n+1) ans+=cnt[x],x=to[x];    printf("%d\n",ans);    return ;}void change() {    int x=rd()+1,k=rd();    da[x]=k;    R(i,l[bl[x]],x) //1        if(i+da[i]>n) cnt[i]=1,to[i]=n+1;        else if(i+da[i]>r[bl[i]]) cnt[i]=1,to[i]=i+da[i];        else cnt[i]=cnt[i+da[i]]+1,to[i]=to[i+da[i]];}int main() {    n=rd(); blo=sqrt(n);    F(i,1,n) da[i]=rd(),bl[i]=(i-1)/blo+1;    init();    q=rd();    while(q--) {        int opt=rd();        if(opt==1) query(rd()+1);        else change();    }    return 0;}