#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
void DisCountSort(vector<int> &arr, int n)
{
    auto _max = max_element(arr.begin(), arr.end());
    int max_val = *_max;
    arr.clear(); // begin to sort arr
    vector<int> c(max_val + 1, 0); // number of times that index value appears
    for (int i = 0; i < n; ++i) c[arr[i]] += 1;
    auto it = arr.begin();
    for (int i = 0; i < max_val + 1; ++i) {
        if (c[i] > 0) {
            arr.insert(it, c[i], i);
            it = arr.end();
        }
 
    }
}
 
int main()
{
    vector<int> arr;
    for (int i = 0; i < 1000111; i++)
    	arr.push_back(1);
    DisCountSort(arr, arr.size());
    cout << "DONE SORTING" << endl;
    return 0;
}
 

I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8dmVjdG9yPgojaW5jbHVkZSA8YWxnb3JpdGhtPgoKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCnZvaWQgRGlzQ291bnRTb3J0KHZlY3RvcjxpbnQ+ICZhcnIsIGludCBuKQp7CiAgICBhdXRvIF9tYXggPSBtYXhfZWxlbWVudChhcnIuYmVnaW4oKSwgYXJyLmVuZCgpKTsKICAgIGludCBtYXhfdmFsID0gKl9tYXg7CiAgICBhcnIuY2xlYXIoKTsgLy8gYmVnaW4gdG8gc29ydCBhcnIKICAgIHZlY3RvcjxpbnQ+IGMobWF4X3ZhbCArIDEsIDApOyAvLyBudW1iZXIgb2YgdGltZXMgdGhhdCBpbmRleCB2YWx1ZSBhcHBlYXJzCiAgICBmb3IgKGludCBpID0gMDsgaSA8IG47ICsraSkgY1thcnJbaV1dICs9IDE7CiAgICBhdXRvIGl0ID0gYXJyLmJlZ2luKCk7CiAgICBmb3IgKGludCBpID0gMDsgaSA8IG1heF92YWwgKyAxOyArK2kpIHsKICAgICAgICBpZiAoY1tpXSA+IDApIHsKICAgICAgICAgICAgYXJyLmluc2VydChpdCwgY1tpXSwgaSk7CiAgICAgICAgICAgIGl0ID0gYXJyLmVuZCgpOwogICAgICAgIH0KCiAgICB9Cn0KCmludCBtYWluKCkKewogICAgdmVjdG9yPGludD4gYXJyOwogICAgZm9yIChpbnQgaSA9IDA7IGkgPCAxMDAwMTExOyBpKyspCiAgICAJYXJyLnB1c2hfYmFjaygxKTsKICAgIERpc0NvdW50U29ydChhcnIsIGFyci5zaXplKCkpOwogICAgY291dCA8PCAiRE9ORSBTT1JUSU5HIiA8PCBlbmRsOwogICAgcmV0dXJuIDA7Cn0K