#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;
}