解题思路

公式化简

W = ∑(i=2..n) $a_i$ + ∑(i=2..n) $a_{i-1}$ = (∑a) - $a_1$ + (∑a) - $a_n$ = 2∑a - ( $a_1$ + $a_n$ )

• 要使 W 最大：让两端之和 $a_1$ + $a_n$ 最小 ⇒ 把最小的两个数放两端。
• 要使 W 最小：让两端之和最大 ⇒ 把最大的两个数放两端。

无需排序，只需一次遍历统计总和、最小两数、最大两数。

题目内容

小欧有一个长度为 $n$ 的数组 {$a_1,a_2,...,a_n$} ;

小欧定义数组的 权值 为 $\sum^n_{i=2}(a_i+ a_{i-1})$ ;

请你将该数组任意重新排序，问能够获得的新数组的最大权值和最小权值各是多少。

输入描述

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

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

输出描述

输出两个整数，用空格分隔，第一个表示重新排列后可获得的最大权值，第二个表示最小权值。

样例1

输入

3
1 2 3

输出

9 7