CSES - Datatähti Open 2018 - Forest Metro
  • Time limit: 1.00 s
  • Memory limit: 512 MB
A new metro connection between Metsälä ja Syrjälä has finally been opened. There are $n$ stations on the line; the first station is Metsälä and the last station is Syrjälä.

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.


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.


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.


5 3 4 6

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$