You and your friend are playing a game on a line of ~N~ stones. Each stone has a value ~v_i~. Alternating turns, starting from you, the following move is performed until there are no more stones:

• If there is only one stone, take that stone.
• Otherwise, take either stone ~1~ or stone ~2~.
  • If stone ~1~ is taken, stone ~2~ becomes the new stone ~1~, stone ~3~ becomes the new stone ~2~, etc.
  • If stone ~2~ is taken, stone ~3~ becomes the new stone ~2~, stone ~4~ becomes the new stone ~3~, etc.

The goal of the game is to take the stones such that the sum of stones' value is the maximum. If both of you play optimally, what is the maximum sum of the stones' value can you achieve?

Input Specification

The first line will contain the integer ~N~ ~(1 \le N \le 10^5)~, the number of stones.

The second line will contain ~N~ integers, ~v_i~ ~(1 \le v_i \le 10^9)~, the values of stones. The first integer is the value of stone ~1~, the second is stone ~2~, etc.

Output Specification

Output the maximum sum of stones' value that you take if both you and your friend play optimally.

Sample Input

5
1 3 2 4 5

Sample Output

8