|시간 제한||메모리 제한||제출||정답||맞힌 사람||정답 비율|
|1 초||256 MB||112||55||44||48.889%|
Byteasar the hacker has qualified for this year’s IHO, the International Hacking Olympiad. One of the tasks in the Olympiad involves competing against a system operator. There are n computers numbered from 1 to n, connected in a ring topology, i.e. computers i and i+ 1 are connected (for i = 1, . . . , n−1), and also computers n and 1 are connected.
The competition is performed as a game between the hacker and the system operator:
Every computer i has a certain value vi which specifies the value of the data which is stored on it. For each hacked computer i, Byteasar scores its value vi. Byteasar is quite a good hacker, but has no idea of algorithms. That is why he asks you to write a program that computes his maximum possible score, assuming that the operator plays optimally.
The first line of input contains a positive integer n (n ≥ 2), specifying the number of computers. The second line contains a sequence of n integers v1, v2, . . . , vn (1 ≤ vi ≤ 2000); number vi specifies the value of the data stored on computer i.
In the first and only line of output your program should write one integer: Byteasar’s maximum possible score against an optimally playing operator.
n ≤ 300
n ≤ 5000
n ≤ 500 000, hacking computer 1 is optimal as Byteasar’s first move
n ≤ 500 000
4 7 6 8 4
5 1 1 1 1 1
In the first example, Byteasar in his first move should hack computer 2 (scoring 6). The operator’s response will be protecting computer 3. In the next move Byteasar can hack computer 1 (scoring 7). Finally, the operator will protect computer 4.