这是问题的硬性版本两个版本の间的区别在于，简单版本没有交换操作只有解决了所有版本的问题，您才可以进行破解

皮卡丘是生活在野生皮卡丘群中的可爱友好嘚神奇宝贝。

但是最近众所周知臭名昭著的R队想偷走所有这些神奇宝贝！神奇宝贝训练师安德鲁决定帮助皮卡丘组建一支反抗神奇宝贝嘚军队。

首先安德鲁算出了所有的神奇宝贝-皮卡丘正好是n个。第i个神奇宝贝的力量等于ai并且所有这些数字都是不同的。

作为一支军队安德鲁可以选择任何非空的神奇宝贝子序列。换句话说安德鲁从k个索引中选择了一些数组b，使得1≤b1<b2 <?<bk≤n他的军队将由力量为ab1，ab2…，abk的神奇宝贝组成

安德鲁正在尝试神奇宝贝秩序。他执行q次运算在第i次行动中，安德鲁交换了第口袋妖怪和第ri个口袋妖怪

安德鲁想知道他在最初的神奇宝贝放置后可以达到的最大步兵力量。他还需要知道每次手术后的最大力量

帮助安德鲁和神奇宝贝或R团队实现他们嘚棘手计划！

我C1是用DP过的，C2是在C1的基础上带修改这里是C1的转移：

C2带转移的话就根据这个方程造一个2*2的矩阵，观察转移式子不难推出右上角是-a[i]左下角是a[i]。但比赛的时候死活过不去样例看来红名大神们的代码才发现，用线段树维护带max的矩阵乘法时要加一步很重要的松弛操莋具体看代码。