E. Swap and Taketime limit per test2 secondsmemory limit per test1024 megabytesinputstandard inputoutputstandard outputYou're given an array consisting of n integers. You have to perform n turns.Initially your score is 0.On the i-th turn, you are allowed to leave the array as it is or swap any one pair of 2 adjacent elements in the array and change exactly one of them to 0(and leave the value of other element unchanged) after swapping. In either case(whether you swap or not), after this you add a_i to your score. What's the maximum possible score you can get?InputThe first line contains a single integer n (2 \le n \le 500).The second line contains n integers a_1, a_2, \ldots, a_n (1 \le a_i \le 10^6).OutputPrint a single integer — the maximum possible score.ExamplesInput
2
3 1
Output
6
Input
5
7 3 9 6 12
Output
52
NoteIn the first example, to get the maximum score we do as follows. Do nothing on the first turn, add 3 to the score. Swap the first and the second elements and turn 1 to 0 on the second turn, and add 3 to the score. The final score is 6.
2
3 1

6 
['dp', 'greedy', '*2600']