F. 排列翻转
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

给定一个长度为 $$$n$$$ 的排列 $$$a_1, a_2, \dots, a_n$$$。为了方便描述边界情况，我们定义 $$$a_0 = 0$$$ 且 $$$a_{n+1} = 0$$$。

你可以对该序列进行无限次操作（包括零次）。每次操作的具体规则如下：

  1. 选择一个区间 $$$[l, r]$$$ $$$(1 \le l \le r \le n)$$$。
  2. 该区间必须满足条件：区间内的所有元素都严格大于区间外侧紧邻的边界元素，即对于 $$$\forall i \in [l, r]$$$，均有 $$$a_i \gt \max(a_{l-1}, a_{r+1})$$$。
  3. 将选定的区间 $$$[l, r]$$$ 进行翻转。即把序列由： $$$$$$ a_1, \dots, a_{l-1}, \underbrace{a_l, a_{l+1}, \dots, a_{r-1}, a_r}_{\text{区间 } [l, r]}, a_{r+1}, \dots, a_n $$$$$$ 变为： $$$$$$ a_1, \dots, a_{l-1}, \underbrace{a_r, a_{r-1}, \dots, a_{l+1}, a_l}_{\text{翻转后的区间 } [l, r]}, a_{r+1}, \dots, a_n $$$$$$

请你求出，经过任意次合法操作后，表达式 $$$\sum_{i=1}^n i \times a_i$$$ 所能取到的最大值和最小值。

Input

第一行输入一个正整数 $$$n$$$ $$$(1 \le n \le 2 \times 10^5)$$$，表示排列的长度。

第二行输入 $$$n$$$ 个正整数 $$$a_1, a_2, \dots, a_n$$$，表示给定的排列。

Output

输出一行两个正整数，用空格隔开，分别表示给定序列经过操作后 $$$\sum_{i=1}^n i \times a_i$$$ 的最大值和最小值。

Example
Input
6
4 3 1 5 2 6
Output
80 67
Note

对于给定的初始序列 $$$[4, 3, 1, 5, 2, 6]$$$：

  • 求最大值：可以通过操作 $$$[4, 3, 1, 5, 2, 6] \to [3, 4, 1, 5, 2, 6]$$$，由此得到最大值。
  • 求最小值：可以通过操作 $$$[4, 3, 1, 5, 2, 6] \to [6, 2, 5, 1, 3, 4] \to [6, 2, 5, 1, 4, 3]$$$，由此得到最小值。