G. 序列分段

小 A 有一个序列 ，他要进行 次下面两种操作之一：

• 1 x y 表示将 修改为 。

• 2 x y 表示小 A 要将 分成三段 ，并且这样操作的代价是三段序列最大值的和，即 。

保证 。

小 A 想要你回答他这次操作所需的最小代价是多少。

第一行两个整数 ，表示序列的长度和操作的次数。

第二行一共 个整数，表示

接下来 行，每行表示一共操作，形式如题。

对于每个操作 ，输出最小代价是多少。

样例一

输入

7 7
4 3 1 1 4 5 2
2 1 7
1 3 5
2 2 4
2 3 5
1 6 1
2 1 5
2 4 7

输出

10
9
10
10
7

样例 2

见附加文件

对于所有数据 。

保证在任意时刻 ，且操作 的 和 为奇数。