RDWAD

内存限制：256 MiB 时间限制：30 Sec

提交提交记录讨论

队(dou)友(bi)翻译了一道题，题面是这样的：

·给定一个长度为n的整数序列a[i]，其中|a[i]|<=1。

·操作：选择一个1<=i<n，令a[i+1]增加a[i]，这个过程中允许|a[i]|>1。

·目标：用最少的操作使得a不降，输出操作数。如果不可行，输出-1。

龙泉寺法师：这么简单？你是看错题了吧？

队(dou)友(bi)：啊……说不定是吧……

龙泉寺法师：这题一定是这样的~(balabala)

·给定一个长度为n的整数序列a[i]，其中|a[i]|<=1

·有m个要求

·第一种要求是将某一个a[i]修改成x(|x|<=1)

·第二种要求是询问[l,r]这一段用最少的操作数使它变得不降。如果不可行，输出-1。

于是，龙泉寺法师迅速把龙泉寺敌法从电脑前踹开，自己开始编写这题的AC算法……

队(dou)友(bi)：这题我不会啊。。

现在请你帮助队(dou)友(bi)解决这道题。

第一行两个数n,m，空格分隔，表示序列长度和操作数。

第二行n个数，表示序列a，满足|a[i]|<=1

接下来m行，每行3个数

如果是第一种要求，四个数0 wi xi，空格分隔，表示把a[wi]修改成xi。

如果是第二种要求，三个数1 li ri，空格分隔，表示询问[li,ri]这一段至少要多少次操作才能不降。如果不可行，输出-1。

对于每个第二种要求，输出一行，包含一个数，表示询问的答案。

为了避免可能的空输出问题，最后输出一行，表示额外的一个询问1 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

最后输出整体的答案：操作3次变为-1 -1 -1 -1 0 1，输出3

n,m<=1000000

建议使用读入优化

#3951. RDWAD

题目描述

输入格式

输出格式

样例

样例输入

样例输出

数据范围与提示