题目背景

黑客梦梦有机会参加黑客比赛。比赛中，梦梦与熊熊对抗，目标是黑掉环状连接的计算机。操作规则如下：

梦梦首先操作，之后双方交替操作。

• 梦梦首次操作可以选择任意计算机进行黑掉。
• 熊熊首次操作可以选择任意未被黑掉的计算机进行保护。

后续操作中，梦梦可以：

• 什么都不做，或
• 黑掉未被黑掉且与被黑计算机直接相连的计算机。

后续操作中，熊熊可以：

• 什么都不做，或
• 保护未被黑掉且与被保护计算机直接相连的计算机。

如果连续两轮双方都选择不操作，游戏结束。初始状态：所有计算机既未被黑掉也未被保护。

每台计算机有一个价值，梦梦通过黑掉计算机获得相应分数。梦梦需要一个程序来计算他的最大可能得分，假设熊熊采取最佳策略。

输入格式

输入的第一行包含一个正整数n，表示计算机台数。

第二行是一个n个正整数的序列$v_i$，$v_i$表示计算机i上存储的数据价值。

输出格式

一行一个整数，表示梦梦获得的最大可能得分。

数据范围

对于所有数据满足，$2\leq{n},1\leq{v_i}\leq{2*10^3}$

对于20%的数据，$n\leq{300}$；

对于60%的数据，$n\leq{5*10^3}$；

对于100%的数据，$n\leq{5*10^5}$；

样例

4
7 6 8 4

13

5
1 1 1 1 1

3

时间空间限制

1000ms，262144K