解题思路

问题转化
每次操作是在一个连续子段 $[l, r]$ 内任意重排元素，消耗为该子段内元素之和。
如果把整个序列划分成若干不相交的区间分别操作，且每个元素至多被操作一次，总消耗就是这些区间内所有元素之和。
设序列总和为 $S$ ，未被操作的元素（即保留在原位的元素）总和为 $S_{\text{keep}}$ ，则总消耗等于 $S - S_{\text{keep}}$ 。
因此最小化总消耗等价于最大化可保留在原位的元素之和。
可保留元素的条件

题目内容

你获得了一个长度为 $n$ 的整数序列 $x_1, x_2, \dots, x_n$ 。你可以进行任意次调整操作：每次选择一个连续子段 $[l, r]$ （ $1 \le l \le r \le n$ ），将该子段内的元素按任意顺序重排。这次调整的消耗等于该子段所有元素之和。

你需要分别求出：

约束：序列长度 $n$ 不超过 $2 \times 10^5$ ，所有元素 $x_i$ 的值在 $1$ 到 $10^9$ 之间。