/* 解析见挑战P48-49
法一:递归--复杂度(O(n^2))
*/
#include <iostream>
typedef long long ll;
const int MAX_N = 2e4 + 10;
int N, L[MAX_N];
using namespace std;
void show()
{
for (int i = 0; i < N; i++)
cout << L[i] << " ";
cout << endl;
}
void solve()
{
ll ans = 0;
// 直到计算模板为1块为止
while ( N > 1 )
{
// 求出最短的板的下标mii1,和次短的板的下标mii2
int mii1 = 0, mii2 = 1;
if ( L[mii1] > L[mii2] ) swap(mii1, mii2);
for ( int i = 2; i < N; i++ )
{
if ( L[i] < L[mii1] )
{
mii2 = mii1;
mii1 = i;
}
else if ( L[i] < L[mii2] )
{
mii2 = i;
}
}
// show();
// 将两块板拼合
int t = L[mii1] + L[mii2];
ans += t;
// cout << L[mii1] << " " << L[mii2] << endl;
// cout << "ans = " << ans << endl;
if (mii1 == N - 1) swap(mii1, mii2);
L[mii1] = t;
L[mii2] = L[N - 1];
// cout << "after changed: " << L[mii1] << " " << L[mii2] << endl;
// cout << "mii1 = " << mii1 << " mii2 = " << mii2 << endl;
// show();
N--;
}
cout << ans << endl;
}
int main()
{
cin >> N;
for ( int i = 0; i < N; i++ )
{
cin >> L[i];
}
solve( );
return 0;
}
//法二:见挑战 P77
//改进:使用优先队列 复杂度O(nlogn)
#include <iostream>
#include <queue>
typedef long long ll;
const int MAX_N = 2e4 + 10;
int N, L[MAX_N];
using namespace std;
typedef long long ll;
typedef priority_queue<int, vector<int>, greater<int> > QUEUE;
//void test(QUEUE a)
//{
// while (a.size())
// {
// cout << a.top() << endl;
// a.pop();
// }
//}
void solve()
{
ll ans = 0;
// 声明一个从小到大取出数值的优先队列
QUEUE que;
for (int i = 0; i < N; i++)
que.push(L[i]);
// test(que);
// 循环到只剩下一块木板为止
while (que.size() > 1)
{
// 取出最短的木板和次短的木板
int l1, l2;
l1 = que.top();
que.pop();
l2 = que.top();
que.pop();
// 把两块木板合并
ans += l1 + l2;
que.push(l1 + l2);
// test(que);
}
cout << ans << endl;
}
int main()
{
cin >> N;
for ( int i = 0; i < N; i++ )
{
cin >> L[i];
}
solve( );
return 0;
}