p203.ans1
======================
8

=================
p203.cpp
======================
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

int n;
vector<int64_t> freq;

void read() {
    cin >> n;
    freq.resize(n);
    cin >> freq;
}

void solve() {
    // - The encoded length equals the sum, over every internal node of the
    //   Huffman tree, of that node's mark; equivalently each merge adds the
    //   combined weight to the total.
    //
    // - Since the frequencies arrive already sorted, run the classic two-queue
    //   Huffman: q1 holds the original leaves in order and q2 holds the merged
    //   nodes in nondecreasing order. The two smallest active nodes are always
    //   at the fronts of q1 and q2, so each step pops the two smaller fronts,
    //   adds their sum to the total bit count, and pushes the sum onto q2 until
    //   a single node remains.

    queue<int64_t> q1, q2;
    for(int i = 0; i < n; i++) {
        q1.push(freq[i]);
    }

    int64_t total_bits = 0;
    while(q1.size() + q2.size() > 1) {
        int64_t picked[2];
        for(int i = 0; i < 2; i++) {
            if(q2.empty() || (!q1.empty() && q1.front() < q2.front())) {
                picked[i] = q1.front();
                q1.pop();
            } else {
                picked[i] = q2.front();
                q2.pop();
            }
        }

        int64_t combined = picked[0] + picked[1];
        total_bits += combined;
        q2.push(combined);
    }

    cout << total_bits << '\n';
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}

=================
p203.in1
======================
3
1 1 4

=================
statement.txt
======================
203. Hyperhuffman
time limit per test: 0.25 sec.
memory limit per test: 65536 KB
input: standard
output: standard



You might have heard about Huffman encoding — that is the coding system that minimizes the expected length of the text if the codes for characters are required to consist of an integral number of bits.

Let us recall codes assignment process in Huffman encoding. First the Huffman tree is constructed. Let the alphabet consist of N characters, i-th of which occurs Pi times in the input text. Initially all characters are considered to be active nodes of the future tree, i-th being marked with Pi. On each step take two active nodes with smallest marks, create the new node, mark it with the sum of the considered nodes and make them the children of the new node. Then remove the two nodes that now have parent from the set of active nodes and make the new node active. This process is repeated until only one active node exists, it is made the root of the tree.

Note that the characters of the alphabet are represented by the leaves of the tree. For each leaf node the length of its code in the Huffman encoding is the length of the path from the root to the node. The code itself can be constrcuted the following way: for each internal node consider two edges from it to its children. Assign 0 to one of them and 1 to another. The code of the character is then the sequence of 0s and 1s passed on the way from the root to the leaf node representing this character.

In this problem you are asked to detect the length of the text after it being encoded with Huffman method. Since the length of the code for the character depends only on the number of occurences of this character, the text itself is not given — only the number of occurences of each character. Characters are given from most rare to most frequent.

Note that the alphabet used for the text is quite huge — it may contain up to 500 000 characters.


Input
The first line of the input file contains N — the number of different characters used in the text (2 ≤ N ≤ 500,000). The second line contains N integer numbers Pi — the number of occurences of each character (1 ≤ Pi ≤ 109, Pi ≤ Pi + 1 for all valid i).

Output
Output the length of the text after encoding it using Huffman method, in bits.

Sample test(s)

Input
3
1 1 4

Output
8
Author:	Andrew Stankevich
Resource:	Petrozavodsk Summer Trainings 2003
Date:	2003-08-23




=================
