U556855 崩坏星穹铁道1

题目背景

开拓者到了星穹列车。

题目描述

星穹列车的众人在进行航线会议， 她一回去，星穹列车上的无名客就让她进行了投票，共有n个星球，可以把要去两个星球的人合并到一起，得到的不满值等于要去两个星球的人的人数之和，直到到第n-1个星球。问最小的不满值。

输入格式

共两行。 第一行是一个整数 n(1≤n≤10000) ，表示星球的个数。 第二行包含 n 个整数，用空格分隔，第 i 个整数ai(1≤ai)≤20000) 是要去那个星球的人的人数。

输出格式

一个整数，也就是最小的不满值。

输入输出样例 #1

输入 #1

3 
1 2 9

输出 #1

15