#include <fstream>
#include <vector>
#include <queue>

using namespace std;

ifstream in("huffman.in");
ofstream out("huffman.out");

const int N = 2 * 1000005;

int n, maxlvl, nrn, niv[N];

long long tot,  val[N];

queue <pair <int, long long> > Q1, Q2;

vector <int> L[N];

void read() {
    int x;

    in >> n;

    for (int i = 1; i <= n; ++i) {
        in >> x;
        Q1.push(make_pair(i, x));
    }
}

void make_trie() {
    pair <int, long long> x, y;
    nrn = n;

    while ((Q1.size() > 1 || Q2.size() > 1) || (Q1.size() == 1 && Q2.size() == 1)) {
        if (Q1.empty()) {
            x = Q2.front();
            Q2.pop();

            y = Q2.front();
            Q2.pop();
        } else if(Q2.empty()) {
            x = Q1.front();
            Q1.pop();

            y = Q1.front();
            Q1.pop();
        } else {
            if (Q1.front().second > Q2.front().second) {
                x = Q2.front();
                Q2.pop();
            } else {
                x = Q1.front();
                Q1.pop();
            }

            if (Q1.empty()) {
                y = Q2.front();
                Q2.pop();
            } else if (Q2.empty()) {
                y = Q1.front();
                Q1.pop();
            } else {
                if (Q1.front().second > Q2.front().second) {
                    y = Q2.front();
                    Q2.pop();
                } else {
                    y = Q1.front();
                    Q1.pop();
                }
            }
        }

        ++ nrn;

        L[nrn].push_back(x.first);
        L[nrn].push_back(y.first);

        Q2.push(make_pair(nrn, (long long)x.second + y.second));

        tot += (long long)x.second + y.second;
    }

    out << tot << '\n';
}

int main() {
    read();

    make_trie();

    for (int i = 1; i <= n; ++ i)
        out << 0 << ' ' << 0 << '\n';

    return 0;
}