Migrated from Lutece 2691 Niuma 选妃

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

$\texttt{Niuma}$ 有自己的后宫，虽有后宫佳丽三千但是它依然不满足，于是 $\texttt{Niuma}$ 又打算进行了一次选妃。

这一次一共有 $n$ 个妹子入选，$n$ 个妹子按 $1$ 号到 $n$ 号排成一行，每个妹子都有一个美丽度 $a_i$，由于 $\texttt{Niuma}$ 具有牛马属性，所以他会选走所有的 $n$ 个妹子，但是选择的顺序还没有确定。$\texttt{Niuma}$ 时间紧迫，所以它的选妃过程如下。

一开始 $\texttt{Niuma}$ 位于 $1$ 号妹子面前，然后它将依次经过每个妹子直到 $n$ 号妹子，在这个过程中它可以按顺序依次选择一些妹子出列，接着它会从 $n$ 号妹子出发，倒序经过整个妹子序列，再依次将每个还未出列的妹子出列，于是 $\texttt{Niuma}$ 便得到了一个妹子的出列顺序，作为它的挑选顺序，记为 $b_i$，$b_i$ 是 $n$ 的一个排列。由于 $\texttt{Niuma}$ 癖好独特，现在它希望知道下面这个数 $W$ 的取值范围。

现在给出 $n$ 个妹子的美丽度 $a_i$，$\texttt{Niuma}$ 现在希望你通过构造 $b_i$，给出 $W$ 的取值范围，即最小值和最大值。

Input

第一行一个整数 $n\ (1\le n\le 10^5)$。

第二行 $n$ 个整数，表示 $a_i\ (0\le a_i\le 10^6)$。

Output

一行两个整数 $a$, $b$，用一个空格隔开，分别表示 $W$ 的最小值和最大值。

Samples

5
1 4 2 5 3

36 54

5
1 2 3 4 5

35 55

Note

对于第一组样例，要想 $W$ 取得最小值，需要在走第一遍时，只让美丽度为 $4$ 和 $5$ 的妹子出列，然后返回时让剩下的妹子依次出列，于是得到 $b$ 数组为 $\{2,4,5,3,1\}$，对应的美丽度序列为 $\{4,5,3,2,1\}$，这时美丽度最小为 $36$；最大值情况是 $b$ 序列为 $\{1,3,5,4,2\}$，此时美丽度为 $54$。

Resources

电子科技大学第十二届 ACM 趣味程序设计竞赛