4400. [CCPC 2026 HA] 排列反转

Problem B. 排列翻转

Input file: $\verb|standard input|$

Output file: $\verb|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$ 的最大值和最小值。

Examples

6
4 3 1 5 2 6

80 67

Note

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

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