题解
题面描述
给定一个长度为 n 的数组 {a1,a2,…,an}。可以进行若干次如下操作：
- 任选一个区间 [l,r]，将子数组 {al,al+1,…,ar} 的所有元素任意重排；
- 本次操作代价为该区间元素之和：
i=l∑rai.
要求计算：
P2908.第2题-数组重新排序
题目内容
小红有一个长度为 n 的数组 {a1,a2,...,an}。她可以对数组进行若干次如下操作，每次操作步骤：
-
选取一个区间 [l,r]，即子数组 {al,al+1,...,ar}；
-
将该子数组中的所有元素以任意顺序重新排序；
-
本次操作需支付代价 ∑i=1rai=al+al+1+...+ar 。
请你分别计算出：
输入描述
第一行输入一个整数 n(1≦n≦2×105) ，表示数组长度。
第二行输入 n 个整数 a1,a2,...,an(1≦ai≦109) ，老示数组元素。
输出描述
在一行上输出两个整数，分别表示将原数组按从小到大排序的最小总代价，将原数组按从大到小排序的最小总代价。
样例1
输入
3
1 2 4
输出
0 7
说明
从小到大的情况无需操作。
从大到小的情况需要选中整个数组，然后按照 [4,2,1] 排序，代价为 1+2+4=7 。
