题目描述

给定一个长度为 $n$ 的整数序列 $a_{1\cdots n}$，其中 $|a_i|\leq 1$。

有 $m$ 次操作，每次是下面两种格式之一：

• 0 x y，表示把 $a_x$ 修改为 $y$。
• 1 l r，表示询问区间 $[l,r]$ 至少需要操作多少次才能变得单调不降，不可行则输出 -1。定义一次操作为选择一个 $i\in[1,n-1]$，$a_{i+1}\leftarrow a_{i+1}+a_i$。

输入格式

第一行两个整数 $n,m$，表示序列长度和操作次数。

接下来一行 $n$ 个整数 $a_{1\cdots n}$。

接下来 $m$ 行，每行三个整数表示一个操作，意义见题目描述。

输出格式

对于每组询问输出一行一个整数表示答案。

在完成 $m$ 次操作之后，请额外输出一行表示询问区间 $[1,n]$ 的答案。

6 6
1 1 0 -1 0 1
1 1 4
0 1 -1
0 2 -1
1 1 4
1 3 5
0 2 1

3
1
-1
3

样例解释

1. 询问 1 1 0 -1，操作 $3$ 次变成 1 1 1 1，输出 3；
2. 修改 $a_1$ 为 -1，序列为 -1 1 0 -1 0 1；
3. 修改 $a_2$ 为 -1，序列为 -1 -1 0 -1 0 1；
4. 询问 -1 -1 0 -1，操作 $1$ 次变成 -1 -1 -1 -1，输出 1；
5. 询问 0 -1 0，前两个位置不可能非递减，无解，输出 -1；
6. 修改 $a_2$ 为 1，序列为 -1 1 0 -1 0 1；
7. 最后输出整体的答案：操作 $3$ 次变为 -1 -1 -1 -1 0 1，输出 3。

数据规模与约定

对于 $100\%$ 的数据，$1\leq n,m\leq 10^6$。