题目描述

给定一个正整数 $n$ 和一个长度为 $n$ 的非递增序列 $a_i$，满足： $\forall i \in [1, n - 1],\ a_i \ge a_{i+1}$。

给定正整数 $m$，表示总操作次数，共有两种操作：

• 操作 0：输入整数 $x$（满足 $1 < x < n$），将 $a_x$ 修改为 $a_{x-1} + a_{x+1} - a_x$。
• 操作 1：查询操作，输入整数 $k$。要求将序列恰好分成 $k$ 段，每段长度至少为 1；每段的权值定义为该段最大值与最小值的差值，你需要输出所有合法分段方式中，$k$ 段权值总和的最小值。

每次操作先输入操作类型：0 代表第一种修改操作，1 代表第二种查询操作。

输入格式

第一行输入正整数 $n$（$3 \le n \le 10^6$），表示序列长度。 第二行输入 $n$ 个正整数 $a_1,a_2,\dots,a_n$（$1 \le a_i \le 10^9$）。 第三行输入正整数 $m$（$1 \le m \le 10^6$），表示操作总次数。 接下来 $m$ 行，每行格式为：

• 0 x：执行修改操作（$1 < x < n$）
• 1 k：执行查询操作（$1 \le k \le n$）

输出格式

对于每一个查询操作，单独输出一行一个整数，表示对应查询的答案。

Samples

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

17
7

Limitation

1s, 1024KiB for each test case.