### 问题描述 小蓝在星际旅游的时候发现了排列成一排的 $n$ 颗星星，每颗星星都有自己的美丽值 $a_i$，小蓝可以无限次进行这两种操作中的任一种： 1. 将任意一颗星星变成黑洞，黑洞会将左右的星星吸走（若只有一侧有星星，则只会吸走该侧星星），然后诞生一颗有着被吸走星星美丽值之和的新星星。 2. 交换任意星星的位置。 小蓝现在需要你的帮助，请输出当只剩下一颗星星时，它可能达到的最大的美丽值是多少？ ### 输入格式 第一行包含两个整数 $n$，表示星星的个数。 接下来输入 $n$ 个整数表示星星的美丽值。 ### 样例输入 ``` 4 4 3 2 1 ``` ### 样例输出 ``` 7 ``` ### 说明 首先将星星排列成 $[4,1,3,2]$，将 $1$ 变成黑洞，操作完成后会变成 $[7,2]$。 接下来将 $2$ 变成黑洞，这样最后只剩下一颗星星 $[7]$，这是最大的结果。 ### 评测数据规模 对于所有评测数据，$1 \leq n \leq 10^{5}$，$1 \leq a_i \leq 10^{9}$。