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 Python