#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

void radixSort(vector<int> &a) {
    int max = a.at(0);
    for(int i = 0; i < a.size(); ++i) if(int(fabs(a.at(i) > max))) max = a.at(i);
    //hardokodiranjem bi rijesili problem donje granice za tip podatka int
    for(int stepen = 1; max / stepen > 0; stepen *= 10) {
        int sorting[10]{};
        std::vector<int> b = a;
        for(int i = 0; i < a.size(); ++i) sorting[(a.at(i) / stepen) % 10]++;
        for(int i = 1; i < 10; ++i) sorting[i] += sorting[i - 1];
        for(int i = a.size() - 1; i >= 0; --i) {
            b[sorting[(a.at(i) / stepen) % 10] - 1] = a[i];
            sorting[(a.at(i) / stepen) % 10]--;
        }
        a = b;
    }
}

int roditelj(int i) {
    return int(floor((i - 1) / 2));
}

int lijevo_dijete(int i) {
    return 2 * i + 1;
}

int desno_dijete(int i) {
    return 2 * i + 2;
}

bool je_li_list(std::vector<int> a, int i) {
    return (i >= a.size() / 2) && i < a.size();
}

void popravi_dolje(std::vector<int> &a, int i, int velicina) {
    while(!je_li_list(a, i)) {
        int veci = lijevo_dijete(i);
        int dd = desno_dijete(i);
        if(dd < velicina && a.at(dd) > a.at(veci)) veci = dd;
        if(a.at(i) > a.at(veci)) return;
        swap(a.at(i), a.at(veci));
        i = veci;
    }
}

void stvoriGomilu(vector<int> &a) {
        for(int i = int(floor(a.size() / 2)); i >= 0; --i) popravi_dolje(a, i, a.size());
}

void popravi_gore(std::vector<int> &a, int i, int velicina) {
    while(i && a.at(i) > a.at(roditelj(i))) {
        swap(a.at(i), a.at(roditelj(i)));
        i = roditelj(i);
    }
}

void umetniUGomilu(vector<int> &a, int umetnuti, int &velicina) {
    a.push_back(umetnuti);
    velicina++;
    popravi_gore(a, velicina - 1, velicina);
    stvoriGomilu(a);
}

int izbaciPrvi(vector<int> &a, int &velicina) {
    if(velicina == 0) throw domain_error("Gomila je prazna!");
    velicina--;
    int temp = a.at(0);
    a.at(0) = a.at(velicina);
    a.at(velicina) = temp;
    if(velicina) popravi_dolje(a, 0, velicina);
    return a[velicina];
}

void gomilaSort(vector<int> &a) {
    stvoriGomilu(a);
    int velicina = a.size();
    for(int i = a.size() - 1; i >= 1; --i) {
        int temp = a.at(i);
        a.at(i) = a.at(0);
        a.at(0) = temp;
        velicina--;
        popravi_dolje(a, 0, velicina);
    }
}