小 A 有一个序列 ，他要进行 次下面两种操作之一：
1 x y 表示将 修改为 。
1 x y
2 x y 表示小 A 要将 分成三段 ，并且这样操作的代价是三段序列最大值的和，即 。
2 x y
保证 。
小 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
见附加文件
对于所有数据 。
保证在任意时刻 ，且操作 的 和 为奇数。
