Competitions

# БГУ Личное Первенство

# Cards game

Huseyn and Yaroslav play cards. There are n cards in a row on the table with different numbers written on them. They take turns. Huseyn starts the game. In one move, a player can take either the leftmost or the rightmost card. The player always takes the card with the highest number. The game ends when there are no cards left on the table. Print the sum of the numbers on Huseyn's and Yaroslav's cards.

## Input data

The first line contains the number of cards n\:(1 \le n \le 10000) on the table. The second line contains n positive integers written on the cards. All numbers are not greater than 10^9.

## Output data

Print the sum of the numbers on Huseyn's and Yaroslav's cards at the end of the game.

## Examples

Input example #1

7 4 7 5 1 12 8 2

Output example #1

18 21