\(O(N)\) 時間で解けます．本コンテストの主旨からは外れますが，興味のある方は勉強してみてください．

https://www.mimuw.edu.pl/~idziaszek/termity/termity.pdf

結論は次の通りです．

• 列のうちこの順に隣接する \(3\) 項 \(a,b,c\) で \(a\leq b\geq c\) となっている部分があれば，これを \(a-c+b\) に置き換えても答は変わらない．\((\ldots, a, b, c, \ldots) \to (\ldots, a-b+c,\ldots)\)．
• 上の操作を可能な限り行うと，列は \(a_1 \geq \cdots \geq a_k \leq \cdots \leq a_N\) を満たすものに変形できる．
• この場合，取れる数のうち大きい方をとっていく貪欲戦略によって正しい解を求めることが出来る．

類題：

• https://yukicoder.me/problems/no/1154, https://qoj.ac/contest/1245/problem/6514

（2 つは同じ問題です）