题解

题面描述

给定一个长度为 $n$ 的数组 $\{a_1,a_2,\dots,a_n\}$。可以进行若干次如下操作：

• 任选一个区间 $[l,r]$，将子数组 $\{a_l,a_{l+1},\dots,a_r\}$ 的所有元素任意重排；
• 本次操作代价为该区间元素之和：

$$\sum_{i=l}^r a_i\,.$$

要求计算：

1. 将数组变为升序所需的最小总代价；

题目内容

小红有一个长度为 $n$ 的数组 {$a_1,a_2,...,a_n$}。她可以对数组进行若干次如下操作，每次操作步骤：

• 选取一个区间 $[l,r]$，即子数组 {$a_l,a_{l+1},...,a_r$}；

• 将该子数组中的所有元素以任意顺序重新排序；

• 本次操作需支付代价 $\sum_{i=1}^{r} a_i=a_l+a_ {l+1}+...+a_r$ 。

请你分别计算出：

• 进行若干次操作后，使得新的数组按从小到大排序的最小总代价；

• 进行若干次操作后，使得新的数组按从大到小排序的最小总代价。

输入描述

第一行输入一个整数 $n(1≦n≦2×10^5)$ ，表示数组长度。

第二行输入 $n$ 个整数 $a_1,a_2,...,a_n(1≦a_i≦10^9)$ ，老示数组元素。

输出描述

在一行上输出两个整数，分别表示将原数组按从小到大排序的最小总代价，将原数组按从大到小排序的最小总代价。

样例1

输入

3
1 2 4

输出

0 7

说明

从小到大的情况无需操作。

从大到小的情况需要选中整个数组，然后按照 $[4,2,1]$ 排序，代价为 $1+2+4=7$ 。