题目描述

通过层层选拔，江桥集训队 选出了 $n$​​​​ 名选手，所有选手都会以组队的方式参加比赛，每个队伍都不能超过三人（最少一人），且一个人只能属于一个队伍。根据选拔赛中每个人的表现，江桥给每个人分配了一个正整数 $a$​ ​​​来表示他的实力， $a$​​​​ ​​的值越高表示这个人的能力越强。为了照顾实力弱的选手，江桥制定了以下组队策略：

①目前未组队的人中，实力值最低的一个人与实力值最高的两个人组队（如果有多个人实力值相同，从这些人里面任意选择）。

②重复①过程，直到剩下的未组队人数不足三人，如果有至少一人剩余，那么剩下的人自动组成一队。

显然，最终可以组成 $\lceil \frac{n}{3} \rceil$​​ ​个队伍。一个队伍的实力为队伍里三人的实力值之和。现在江桥可以在这 $n$​ ​​个人组队之前施展一次魔法，使某个人的实力值变成所有选手中实力值最大的那个人的实力值，这样，每个队伍的实力值都有可能发生变化。现在江桥想知道，在他施展完魔法之后组队，实力最强的队伍的实力值最高会是多少？

输入格式

第一行包含一个正整数$n$​​，含义如上所述。

第二行包含$n$​​​​​​​个正整数 $a_i$，表示这些人的实力值，相邻两个数字中间以一个空格隔开。

输出格式

一个正整数，表示答案。

5
1 2 3 4 5

12

9
1 2 10 10 99 99 100 100 100

210

样例解释

在第一个样例中，若使第一个人的实力值变成5，组队的情况为$(2,5,5)$，$(3,4)$，队伍实力值最高为12；

若使第二个人的实力值变成5，组队的情况为$(1,5,5)$，$(3,4)$，队伍实力值最高为11；

若使第三个人的实力值变成5，组队的情况为$(1,5,5)$​，$(2,4)$队伍实力值最高为11；

若使第四个人的实力值变成5，组队的情况为$(1,5,5)$，$(2,3)$队伍实力值最高为11；

若使第五个人的实力值变成5，组队的情况为$(1,4,5)$，$(2,3)$队伍实力值最高为10；

因此，实力最强的队伍的实力值最高为12。

数据规模与约定

下发文件

下发文件对应子任务 $5$。

有合理的子任务依赖。

对于 $100\%$ 的数据：保证 $1 \leq n \leq 3 \times 10^5,0 \leq a_i \leq 10^9$。