题目描述

已知数组 $a$ 和数组 $b$ 都是由 $n$ 个非负整数组成的数组，数组 $b$ 中每一个元素 $b_i$ 为数组 $a$ 中前 $i$ 个元素的最大值，即

我们用 $sum=a_1+a_2+\cdots+a_n$ 表示数组 $a$ 的 $n$ 个元素之和。现在告诉你 $b$ 数组，请你根据 $b$ 数组反推 $a$ 数组。$a$ 数组可能并不唯一，请根据 $a$ 数组的所有可能情况，给出 $sum$ 的最小值和最大值分别是多少。

输入格式

第一行一个整数 $n$；第二行 $n$ 个整数 $b_1,b_2,\ldots,b_n$。

输出格式

一行两个空格隔开的整数，分别表示最小值和最大值。

样例 1

输入

6
0 0 5 5 10 10

输出

15 30

样例 2

输入

7
1 2 3 4 5 6 7

输出

28 28

样例 3

输入

5
5 5 5 5 5

输出

5 25

数据范围

$1\le n\le10^5$，$0\le b_1\le b_2\le\cdots\le b_n\le10^9$。