题目描述

数轴上有 $n$ 个弹力装置，编号 $0\sim n-1$，第 $i$ 个弹力系数为 $k_i$（$k_i\ge 1$）。一枚棋子落在装置 $i$ 上时被弹到 $i+k_i$；若 $i+k_i\ge n$ 则被弹出、离开装置区。

处理 $m$ 个操作：

• 1 i：询问棋子从装置 $i$ 出发，被弹几次后弹出界；
• 2 i x：将装置 $i$ 的弹力系数 $k_i$ 改为 $x$。

输入格式

第一行一个整数 $n$。

第二行 $n$ 个正整数 $k_0,k_1,\dots,k_{n-1}$。

第三行一个整数 $m$。

接下来 $m$ 行，每行 1 i 或 2 i x。

输出格式

对每个 1 i 操作输出一行，表示弹出所需次数。

样例

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

2
3

数据范围

$1\le n\le 2\times10^5$，$1\le m\le 10^5$，$1\le k_i,x\le 10^9$。