题目描述

徐老师认为一个序列的极差能够代表这个序列数据的离散程度

极差是指这个序列中最大值减最小值的结果（如果序列只有一个元素，则极差为 $0$)

现在徐老师有一个包含 $n$ 个数字的序列 $a_1 \sim a_n$

他希望将这 $n$ 个数字的序列切割成 $x$ 段，每段至少包含 $1$ 个数字，使得这 $x$ 段序列的极差之和最小

但是这个问题过于简单了，所以徐老师决定强化一下问题，他结合了最近学习的 在线 概念，提出了动态询问

徐老师会在给定序列后，依次给出 $m$ 次操作，操作格式如下：

• 0 x 表示将 $a_x$ 修改为 $a_{x - 1} + a_{x + 1} - a_{x}$，即进行 $a_x = a_{x - 1} + a_{x + 1} - a_{x}$ 的赋值
• 1 x 表示提出一次询问，询问将当前这个序列切割成 $x$ 段（每段至少包含 $1$ 个数字）后，这 $x$ 段序列的极差之和最小是多少

现在徐老师想请你来挑战一下这道题目

P.S. 由于这个问题可能很难，所以徐老师保证给定的序列 $a$ 一定是一个 不增序列，即对于任意两个相邻的数字 $a_i$ 和 $a_{i+1}$ 满足 $a_{i+1} \leq a_i$

输入格式

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

输入第二行包含 $n$ 个整数，表示序列 $a_1 \sim a_n$。

接下来 $m$ 行，每行包含两个整数表示一次操作，操作格式如题所述

输出格式

对于每次询问，输出一个整数表示答案

数据范围

对于 $20\%$ 的数据保证：$1 \leq n,m \le 100$。

对于 $40\%$ 的数据保证：$1 \leq n,m \le 1000$。

另有 $10\%$ 的数据保证：$a_i = 1$

对于 $100\%$ 的数据保证： $1\leq n,m \leq 10^5, 1 \leq a_i \leq 10^9$。

特别的，对于操作 0 x 保证 $1 < x < n$，对于操作 1 x 保证 $1 \leq x \leq n$

样例输入1

5 3
30 20 18 13 2
1 2
0 3
1 3

样例输出1

17
7

样例解释1

对于第一次询问，原序列为 $30,20,18,13,2$，切割成 $[30,20,18,13]$ 和 $[2]$ 可以得到最小的极差之和 $(30-13) + (2-2) = 17$

对于第一次询问，原序列为 $30,20,15,13,2$，切割成 $[30],[20,15,13]$ 和 $[2]$ 可以得到最小的极差之和 $(30-30) + (20-13) + (2-2) = 7$