Jake and Josh are identical twins who have the exact same interests in toys, so Santa has decided to give them ~N~ presents that they can share. However, both boys are very greedy and hate sharing, so they spent all of Christmas morning fighting over who gets which presents. In order to stop the fighting, their parents came up with a way for them to split the presents fairly.

The parents placed the presents in a line and gave Jake a seashell. They told the boys to go through the presents in order and let the person holding the shell decide who gets the current present. However, if one of the boys decides to take a present for himself, he must give the shell to his twin. That is, the person with the shell has one of two choices:

1. Take the current present and give the shell to his twin.
2. Give the current present to his twin and hold onto the shell.

Jake and Josh both know the value of all the presents and want to maximize the total value of the presents they get. If they both split the presents optimally, what is the total value of the presents that Jake will get?

Input

The first line of input contains an integer ~N~ ~(1 \le N \le 100~ ~000)~.

The next line contains ~N~ integers ~V~ ~(1 \le V \le 1~ ~000)~, denoting the value of the presents in the order that the boys will go through them.

Output

The maximum total value of the presents Jake can get.

Sample Input 1

3
1 5 3

Sample Output 1

5

Sample Input 2

5
10 10 1 1 5

Sample Output 2

15