#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{30, 90, 60, 70, 10, 60, 30, 70, 100, 50, 70};
    DisCountSort(arr, arr.size());
    for (auto &it : arr) cout << it << " ";
    return 0;
}
 

I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8dmVjdG9yPgojaW5jbHVkZSA8YWxnb3JpdGhtPgoKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCnZvaWQgRGlzQ291bnRTb3J0KHZlY3RvcjxpbnQ+ICZhcnIsIGludCBuKQp7CiAgICBhdXRvIF9tYXggPSBtYXhfZWxlbWVudChhcnIuYmVnaW4oKSwgYXJyLmVuZCgpKTsKICAgIGludCBtYXhfdmFsID0gKl9tYXg7CiAgICBhcnIuY2xlYXIoKTsgLy8gYmVnaW4gdG8gc29ydCBhcnIKICAgIHZlY3RvcjxpbnQ+IGMobWF4X3ZhbCArIDEsIDApOyAvLyBudW1iZXIgb2YgdGltZXMgdGhhdCBpbmRleCB2YWx1ZSBhcHBlYXJzCiAgICBmb3IgKGludCBpID0gMDsgaSA8IG47ICsraSkgY1thcnJbaV1dICs9IDE7CiAgICBhdXRvIGl0ID0gYXJyLmJlZ2luKCk7CiAgICBmb3IgKGludCBpID0gMDsgaSA8IG1heF92YWwgKyAxOyArK2kpIHsKICAgICAgICBpZiAoY1tpXSA+IDApIHsKICAgICAgICAgICAgYXJyLmluc2VydChpdCwgY1tpXSwgaSk7CiAgICAgICAgICAgIGl0ID0gYXJyLmVuZCgpOwogICAgICAgIH0KCiAgICB9Cn0KCmludCBtYWluKCkKewogICAgdmVjdG9yPGludD4gYXJyezMwLCA5MCwgNjAsIDcwLCAxMCwgNjAsIDMwLCA3MCwgMTAwLCA1MCwgNzB9OwogICAgRGlzQ291bnRTb3J0KGFyciwgYXJyLnNpemUoKSk7CiAgICBmb3IgKGF1dG8gJml0IDogYXJyKSBjb3V0IDw8IGl0IDw8ICIgIjsKICAgIHJldHVybiAwOwp9Cg==