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