← 返回题目列表

Codeforces · 1736/E

E. 交换并获取

中文机器翻译题面 查看原题

给定一个由 $$$n$$$ 整数组成的数组。你必须执行 $$$n$$$ 回合。

最初您的分数是 $$$0$$$。

在第 $$$i$$$ 回合中,您可以保持数组不变,也可以交换数组中任意一对 $$$2$$$ 相邻元素,并在交换后将其中一个恰好更改为 $$$0$$$(并保持其他元素的值不变)。无论哪种情况(无论您是否交换),此后您都将 $$$a_i$$$ 添加到您的分数中。

您可以获得的最高分数是多少?

输入

第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 500$$$)。

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

输出

打印一个整数——可能的最大分数。

示例

输入 #1

2
3 1

输出 #1

6

输入 #2

5
7 3 9 6 12

输出 #2

52

注意

在第一个示例中,为了获得最高分数,我们执行以下操作。第一回合不做任何事情,将 $$$3$$$ 添加到分数中。交换第一个和第二个元素,并在第二回合将 $$$1$$$ 变为 $$$0$$$,并将 $$$3$$$ 添加到分数中。最终得分为$$$6$$$。