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
computers numbered from 1 to
, connected in a ring topology,
i.e. computers
and
are connected (for
), and also computers
and 1 are connected.
The competition is performed as a game between the hacker and the system operator:
At the beginning of the game none of the computers are hacked or protected.
Every computer
has a certain value
which specifies the value of the data which is stored on it.
For each hacked computer
, Byteasar scores its value
.
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
(
), specifying the number of
computers.
The second line contains a sequence of
integers
(
); number
specifies the value of the data stored on computer
.
In the first and only line of output your program should write one integer: Byteasar's maximum possible score against an optimally playing operator.
For the input data:
4 7 6 8 4
the correct result is:
13
For the input data:
5 1 1 1 1 1
the correct result is:
3
Explanation to the examples: 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.
| Subtask | Conditions | Points |
| 1 | | 20 |
| 2 | | 20 |
| 3 | , hacking computer 1 is optimal as Byteasar's first move | 20 |
| 4 | | 40 |
W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem szkopul@fri.edu.pl.
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, odwiedź nasze serwery na Discordzie. Są one moderowane przez społeczność, ale członkowie zespołu wsparcia również aktywnie się tam udzielają.