Two woodworms decided to eat an old wooden fence. The fence consists of $n$ planks, whose heights are not necessarily equal. The woodworms heard from their termite friends that nothing makes a meal more enjoyable than a bit of healthy competition. They decided to play a game and eat the planks in turns. In their turn, a woodworm can eat one of the end planks of the fence or both at once. Knowing that each woodworm chooses planks such that the sum of the heights of the planks they eat throughout the entire game is as large as possible, calculate how much wood each of them will get.

Input

The first line of the input contains an integer $n$ ($1 \le n \le 1\,000\,000$), representing the number of planks in the fence. The second line contains a sequence of $n$ integers $h_{i}$ ($1 \le h_{i} \le 1\,000\,000\,000$), describing the heights of the consecutive planks.

Output

In the first and only line of the output, print two integers. The first one represents the sum of the heights of the planks eaten by the woodworm starting the game, and the second one represents how much wood its opponent will get.

Examples

Input 1

4
5 2 9 3

Output 1

14 5

Note 1

In the first move, the first woodworm can choose the plank with height 5, the one with height 3, or both at once. The optimal move is to eat the plank with height 5. The opponent then eats the planks with heights 2 and 3.