该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

给你一个长度为 $n$ 的序列 $a_1,a_2,...,a_n$，该序列满足以下两个条件：

• $1\le a_i\le 10^9$。
• $\forall 1\le i\lt n,a_i\le a_{i+1}$。

现在给你 $q$ 次指令，指令分为两种：

• $1\space k$：询问将整个序列分成 $k$ 个互不相交的区间（区间长度可以为 $1$），每个区间的代价是该区间最大的数和最小的数的差值，总代价是划分后的 $k$ 个区间的代价之和，问划分成 $k$ 个区间的最小总代价是多少？
• $2\space p\space v$：将 $a_p$ 修改为 $v$，保证修改后的序列满足上述两个条件。

题目满足 $q$ 次类型为 $1$ 的指令中的 $k$ 最多不会超过 $10$ 种。

输入格式

从文件build.in中读取数据。

• 第一行一个整数 $n$.
• 第二行 $n$ 个整数，表示 $a_1,a_2,...,a_n$。
• 第三行一个整数 $q$。

输出格式

输出到文件build.out中。

• 输出若干行，对于每个类型为 $1$ 的指令，输出对应的最小代价。

6
3 8 13 45 64 99
3
1 2
2 5 55
1 2

61
52

数据规模与约定

• 对于测试点 $1\sim 4$：$2\le n\le 300$，$1\le q\le 300$。
• 对于测试点 $5\sim 6$：$2\le n\le 3000$，$1\le q\le 3000$。
• 对于测试点 $7\sim 20$：$2\le n\le 10^5$，$1\le q\le 10^5$。

所有数据保证 $1\le k\le n$。