Hacker

Byteasar the hacker qualified for this year's international hacking olympiad. One of the events is a game against a system operator. There are $n$ computers numbered 1 to $n$, connected in a ring: computer $i$ is connected to computer $i+1$ for $i = 1, \ldots, n-1$, and computer $n$ is connected to computer 1.

The rules of the game are these.

• Byteasar moves first, and afterwards the operator and Byteasar move alternately.
• On his first move Byteasar picks any computer and hacks it.
• On his first move the operator picks any computer that is not hacked and protects it.
• On every later move Byteasar either does nothing, or picks a computer that is neither hacked nor protected and is directly connected to a hacked computer, and hacks it.
• On every later move the operator either does nothing, or picks a computer that is neither hacked nor protected and is directly connected to a protected computer, and protects it.
• The game ends as soon as both players have done nothing in two consecutive moves.

At the start no computer is hacked or protected. Computer $i$ stores data of value $v_i$, and Byteasar scores $v_i$ for every computer $i$ he hacks. Compute the highest score Byteasar can reach when the operator plays optimally.

The first line contains the number of computers $n$. ($2 \le n \le 50\,000$)

The second line contains $n$ integers $v_1, v_2, \ldots, v_n$ separated by spaces, where $v_i$ is the value of the data stored on computer $i$. ($1 \le v_i \le 2000$)

Print one integer: Byteasar's highest score against an optimally playing operator.

In the first example Byteasar hacks computer 2 and scores 6. The operator answers by protecting computer 3. Byteasar then hacks computer 1 and scores 7, and finally the operator protects computer 4.