有 $n$ 个人要在夜间过桥，所有人只有一盏灯。每次最多两个人同时过桥，耗时等于两人中较慢者的过桥时间；灯必须由过桥的人带到另一侧，后续若仍有人未过桥，就需要有人把灯带回。

第 $i$ 个人单独过桥需要 $a_i$ 分钟。求所有人到达对岸所需的最少总时间。

输入格式

第一行一个整数 $n$。

接下来给出 $n$ 个正整数 $a_1,a_2,\ldots,a_n$，可以位于一行或多行。

输出格式

输出最少总时间。

3
1 2 4

7

3 1 2 4

7

2
63580 48749

63580

数据范围

$2\le n\le10^5$，$1\le a_i\le10^5$。