实际难度：入门---

题目背景

link cut tree 只有40pts

出题人说：“年纪轻轻的写什么lct，你说[本题正解]不香吗？”

题目描述

爬山的路上，有 $n$ 个弹跳装置，准确来说，位于第 $i$ 个位置的弹跳装置有一个数值 $a_i$，走上装置后可以可以到位置 $i+a_i$。

你想爬上山的最高峰，也就是你的位置 $\ge n$ 。有 $m$ 个操作：

1 x 询问从 $x$ 出发几下可以弹到山的最高峰。$(x<n)$

2 x y 第 $x$ 的位置的数值变成 $y$。$(x<n)$

注意，数组下标（位置）从零开始

输入格式

第一行两个整数$n$，$m$($0<n\le2 \times 10^5,0<m\le10^6$)

第二行 $n$ 个整数 $a_i$

接下来 $m$ 行描述每个操作

输出格式

对于每个 $2$ 操作输出一行一个整数表示答案，若这是不可能的，输出 $-1$

输入输出样例 #1

输入 #1

1 1
0
1 0

输出 #1

-1

输入输出样例 #2

输入 #2

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

输出 #2

2
3

说明/提示

本题稍微卡常，建议使用快读快写

$0 \le a_i \le10^9$

数据在NOI Linux 下生成

Subtask最小分值、最大时间

总分加和