**Time limit:**1.00 s**Memory limit:**512 MB

The first train travelled from Metsälä to Syrjälä. You know for each station the

*total*number of passenger who either entered or left the train. Based on this information, your task is to find lower and upper bounds for the maximum number of passengers in the train between two stations.

The train was empty at the beginning and end of the journey, and no passenger left the train immediately after entering it at the same station.

**Input**

The first input line contains an integer $n$: the number of stations.

The next line has $n$ integers $x_1,x_2,\ldots,x_n$: the measured number of passengers at each station.

**Output**

Print two integers: the lower and upper bound for the maximum number of passengers.

You can assume that there is at least one way how the passengers could have acted.

**Example**

Input:

`4`

5 3 4 6

Output:

`6 8`

Explanation: In the lower bound there are 5, 2 and 6 passengers between the stations. In the upper bound there are 5, 8 and 6 passengers between the stations.

**Subtask 1 (14 points)**

- $2 \le n \le 10$

- $1 \le x_i \le 10$

**Subtask 2 (28 points)**

- $2 \le n \le 100$

- $1 \le x_i \le 10$

**Subtask 3 (58 points)**

- $2 \le n \le 10^5$

- $1 \le x_i \le 10^9$