CF1736E Swap and Take

给定一个包含 $n$ 个整数的数组。你需要进行 $n$ 次操作。 初始时你的得分为 $0$。 在第 $i$ 次操作时，你可以选择保持数组不变，或者交换任意一对相邻的元素，并在交换后将其中一个元素变为 $0$（另一个元素的值保持不变）。无论你是否进行交换，之后你都需要将 $a_i$ 加入到你的得分中。 你能获得的最大得分是多少？

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

输出一个整数，表示你能获得的最大得分。

在第一个样例中，为了获得最大得分，可以这样操作：第一次操作什么都不做，将 $3$ 加入得分。第二次操作时交换第一个和第二个元素，并将 $1$ 变为 $0$，然后将 $3$ 加入得分。最终得分为 $6$。 由 ChatGPT 4.1 翻译