CF1736E.Swap and Take

You'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?

给你一个由 $n$ 个整数构成的数组。你需要执行 $n$ 轮操作。

初始时，你的得分为 $0$。

在第 $i$ 轮操作中，你可以选择保持数组不变，或者交换数组中任意一对相邻元素，然后在交换后将其中恰好一个元素变为 $0$（另一个元素的值保持不变）。无论你是否执行交换，在该轮操作结束后，你都要将 $a_i$ 加到你的得分上。

你所能获得的最大可能得分是多少？

The 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$).

第一行包含一个整数 $n$（$2 \le n \le 500$）。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 10^6$）。

Print a single integer — the maximum possible score.

输出一个整数——可能得到的最高分数。

In 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$.

在第一个例子中，为获得最高得分，我们按如下方式操作：第一轮不进行任何操作，得分为 $3$；第二轮交换第一个和第二个元素，并将 $1$ 变为 $0$，再得 $3$ 分。最终得分为 $6$。