Expect some short downtimes and small glitches during the first week of February.

Maximum sums P20262

Statement

Write a program that reads a sequence of numbers, and prints the maximum quantity that can be obtained by adding numbers consecutively from the beginning, and the maximum quantity that can be obtained by adding numbers consecutively from the end.

Input

Input consists of several cases. Each case begins with a number $n$ , followed by $n$ integer numbers.

Output

For every case, print two numbers: the maximum quantity that can be obtained by adding zero or more consecutive numbers from the beginning, and the maximum quantity that can be obtained by adding zero or more consecutive numbers from the end.

Public test cases

Input

4   0 1 2 3
6   1 1 -9 2 0 1
5   -5 -3 6 -1 -1

Output

6 6
2 3
0 4

Information

Author: Salvador Roura
Language: English
Translator: Carlos Molina
Original language: Catalan
Other languages: Catalan
Official solutions: C++ Java Python
User solutions: C C++ Java JavaScript Python