Feli得到总部发来的消息，我军特种部队已经截获敌人的一个密码本，但是这个密码本本身是由密码写成的。为了给敌人造成沉重的打击，Feli必须尽快破译密码。

经过一天一夜的探索，Feli发现日军密码本实际上记载着一个数列，而最终密码由这个数列经过某种运算得到。运算是这样的：

1. 把数列从小到大排序。

2. （分拆）在排好序的数列中，任选一个数，这个数将把原数列分成左右两个数列（选出的数不在新数列中，并且新数列有可能为空）。

3. 对每个新数列进行第2步操作，直到最后得到的数列长度都为1，即全部变成单个数。

4. 将第3步得到的每个数*（得到它所需的分拆次数+1），累加得到一个和。

5. 重复2，3，4操作，直到遍历所有的分拆可能，这时，所得的和当中最小的一个就是日军的最终密码。

6. 现在Feli请求你帮助，尽快破译这段密码！

样例说明

1. 数列排序得 1 2 3

2. 选出一个数 2

3. 分拆得

2

/

1 3

此时新的数列（1，3）长度都已经是1，因此无须再分拆

4. 求和，2*1+1*2+3*2=10（2在原数列，故乘1；1和3都经过一次分拆，故乘2）

2. 选出一个数 1

3. 分拆得

1

2 3

2 3中选一个数 2，分拆得

1

2

3

4. 求和，1*1+2*2+3*3=14

……

……

所有和当中最小的是10，故输出10

题后剧情：

在你的帮助下，Feli最终成功地破译出了密码，居然发现这个密码是关于敌人援军的行动方案的内容！我军便按照这个破译后密码的内容指示的地点伏击敌人。结果成功歼灭了敌人刚刚到达的援军。使得敌人的的主力部队孤立无援。在这次战斗后，Feli名声传遍全军。

输入数据第一行为N，N≤1000，表示密码本记录的数列的长度。

下一行共有N个数，即日军密码本记载的数列。

输出数据为一个整数，即日军最终密码。