[Solution] Swap and Take solution codeforces

Swap and Take solution codeforces – You’re given an array consisting of 𝑛n integers. You have to perform 𝑛n turns.

[Solution] Swap and Take solution codeforces

On the 𝑖i-th turn, you are allowed to leave the array as it is or swap any one pair of 22 adjacent elements in the array and change exactly one of them to 00(and leave the value of other element unchanged) after swapping. In either case(whether you swap or not), after this you add 𝑎𝑖ai to your score.

What’s the maximum possible score you can get?

Input

The first line contains a single integer 𝑛n (2𝑛5002≤n≤500).

The second line contains 𝑛n integers 𝑎1,𝑎2,,𝑎𝑛a1,a2,…,an (1𝑎𝑖1061≤ai≤106).

[Solution] Swap and Take solution codeforces

Print a single integer — the maximum possible score.

Examples
input

Copy
2
3 1

output

Copy
6

input

Copy
5
7 3 9 6 12


[Solution] Swap and Take solution codeforces

Copy
52

Note

In the first example, to get the maximum score we do as follows. Do nothing on the first turn, add 33 to the score. Swap the first and the second elements and turn 11 to 00 on the second turn, and add 33 to the score. The final score is 66.