Cards game

Huseyn and Yaroslav are playing a card game. There are $n$ cards laid out in a row on the table, each with a different number written on it. The players take turns. Huseyn starts the game. On each turn, a player can take either the leftmost or the rightmost card. The player will always choose the card with the highest number. The game ends when there are no cards left on the table. Find the sum of the numbers on the cards collected by Huseyn and Yaroslav at the end of the game.

Input

The first line contains the number of cards $n(1\le n\le 10000)$ on the table. The second line contains $n$ positive integers, each indicating the number on a card. All numbers are not greater than $10^9$.

Output

Print the sum of the numbers on the cards collected by Huseyn and Yaroslav at the end of the game.

Examples