Description

最近J国有发生严重海啸，于是C国又要对J国进行人道主义援助了。现在C国要给J国借N艘船用于救灾，但是C国只有2名船长可用于运送船只。为了便于给J国救援的组织，每次C国的2艘船（也许是1艘）一定是一起开到站的，花费时间一最慢的船所花费的时间。而且2名船长将所有船开到后会参加救灾活动。现在为了更快的进行救灾活动，请问怎样调度能使船最快到达J国。且为了不麻烦J国本国救灾人员，2个船长送到2只船后，可能会开1只船回国为了运送其他没运送的船只。船的过去和回来的时间是相同的。

Input

包含多组测试数据 每组数据第一行包含1个正整数n（1<=n<=200000）表示一共有几艘船。 接下来有有n行每行1个数字ai（1<=ai<=100），表示第i艘船从c国开到J国要多久。

Output

输出一个数字表示多少时间。

Sample

Input

4
1
2 
5
10

Output

17

Hint

1开1,2号船过去花费2， 2开2号船回来花费2， 3开3,4号船过去，花费10， 4开1号船回来花费1， 5开1,2号船过去花费2 总花费 2+2+10+1+2=17