Cracker
By Ricardo Oliveira, UFPR 
Brazil
By Ricardo Oliveira, UFPR Brazil
Carol, Carla, Marcos and Leonardo are all roommates. They rocked a party yesterday and, today, they want to split the leftovers between them. While Carol and Carla are discussing about how they will split a certain cake, Marcos and Leonardo will split a package of crackers between them.
The package has N portions. The number of crackers in each portion is not necessary the same. For example, consider the following package. It has N=5 portions that, from the left to the right, have 3, 1, 2, 3 and 2 crackers, respectively.
Marcos will split the package in two parts, cutting the package in some of the N-1 places between two consecutive portions. In the given example, Marcos has 4 possible places to cut, represented by the dotted lines. After the cut, Leonardo will chose which of the two parts he will have. Marcos will then have the other part.
After the cut, Leonardo will chose the part that contains the largest number of crackers. Marcos knows that and, thus, need to chose the place to cut such that the number of crackers he will have is maximized. Help him with this task!
The input contains several test cases. The first line of each test case contains an integer N (2 ≤ N ≤ 105), the number of portions in the package. The second line contains N integers b1, b2, ..., bN (1 ≤ bi ≤ 104), the number of crackers in each portion, from the left to the right.
The input ends with end-of-file (EOF).
For each test case, print a single line with two integers separated by an space, indicating how many crackers Marcos and Leonardo will have, respectively.
| Input Sample | Output Sample |
|
5 |
5 6 |