Hacking the Ring

Byteasar the hacker has qualified for this year’s International Hacking Olympiad (IHO). In one of the tasks he competes against a system operator on a network of n computers arranged in a ring topology. The computers are numbered from \(1\) to \(n\) and for every \(i = 1, \dots, n-1\) computer \(i\) is connected to computer \(i+1\), with an extra connection between computer \(n\) and computer \(1\).

The game is played as follows:

• Byteasar moves first. Then the operator and Byteasar alternate moves.
• On his first move Byteasar hacks an arbitrary computer \(i\).
• Immediately afterwards, the operator protects any one non-hacked computer.
• On every subsequent move, Byteasar can either do nothing or hack any computer that is still neutral (i.e. neither hacked nor protected) and is adjacent to some hacked computer.
• Similarly, on every subsequent move the operator can either do nothing or protect any neutral computer that is adjacent to some already protected computer.
• The game ends as soon as both players choose to do nothing in two consecutive moves.

Each computer \(i\) stores data worth \(v_i\); Byteasar collects \(v_i\) for every computer he manages to hack. Although Byteasar is a good hacker, he is not familiar with algorithms. He asks you to write a program that computes his maximum possible total score, assuming that the operator plays optimally.

Note: The players can only extend their control (hacked or protected) to a computer that is adjacent to a computer they have already acted upon. In the beginning only computer \(i\) is hacked and the operator protects one of its two neighbours. After that the two “fronts” expand in opposite directions along the ring. It turns out that, under optimal play, Byteasar’s additional hacks will be exactly the computers along the free side up to a number equal to \(k = \lfloor (n-1)/2 \rfloor\) (taken in the natural cyclic order). Since the operator can choose which of the two neighbours to protect in his first move, Byteasar’s final gain when starting at computer \(i\) is given by:

[ \text{score}(i) = v_i + \min\Bigl(\sum_{j=1}^{k}v_{(i+j)\bmod n}, ; \sum_{j=1}^{k}v_{(i-j)\bmod n} \Bigr). ]

Your task is to choose the best starting computer \(i\) so that Byteasar’s score is maximized.

inputFormat

The input begins with a single integer \(n\) (\(1 \le n \le 10^5\)) — the number of computers in the ring. The next line contains \(n\) integers \(v_1, v_2, \dots, v_n\) where \(v_i\) is the data value stored on computer \(i\). For \(n = 1\) the only computer is hacked and the game ends immediately.

outputFormat

Output a single integer which is the maximum total score Byteasar can guarantee assuming optimal play by the operator.

sample

3
1 2 3

4