Migrated from Lutece 3155 龙车

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Tag：lct/分块

小$w$最近在玩怪猎，他觉得猫猫太可爱了，于是决定邀请猫猫来玩一个游戏。

小$w$将捕获到的$n$个猎物放成一条直线，第$i$个怪物的力量为$a_i$，意为怪物$i$将会将使用龙车将猫猫撞飞到第$i+a_i$怪物处。如果$i+a_i\geq n$，则游戏结束，猫猫被弹飞的次数作为此次游戏的分数。游戏一开始，猫猫将选择一只怪物作为起始点，猫猫想知道如果选择$i$作为起始，它能得到多少分数。

怪物是会累、会生气的，所以$a_i$是会变化的。当然，$a_i$会一直大于0。

注意怪物的编号为$0\sim n-1$。

Input

第一行包含一个整数$n$，表示怪物的数量。 接下来一行有$n$个整数，依次为$n$个怪物的力量。 第三行包含一个整数$m$，表示操作的数量。 接下来$m$行每一行包含两（三）个整数：$ty，x，y$，含义如下： 若$ty=1$，则$x$表示起始位置，没有$y$。 若$ty=2$，则$x$表示怪物编号，$y$表示怪物改变后的力量。

Output

对于$m$次操作中$ty=1$的操作输出一行一个整数表示此次游戏的分数。

Samples

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

2
3

Constraints

$1\leq n,m,a_i\leq 1\times 10^5$

Resources

2024 UESTC ICPC Training for Data Structure