#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int fragments = 256;

fstream fin("algsort.in");
ofstream fout("algsort.out");

vector<int> initialNumbers;

double EPS = 1e-6;

void akySort(vector<int>& numbers){
    if (numbers.size() < fragments*4){
        sort(numbers.begin(), numbers.end());
        return;
    }

    int maxValue = numbers[0];
    int minValue = numbers[0];
    for (auto const &el : numbers){
        maxValue = max(maxValue, el);
        minValue = min(minValue, el);
    }

    double step = (double)(maxValue-minValue) / (double)(fragments);
    vector<int> buckets[fragments];
    for (auto const &el : numbers){
        int index = max(min((int)((el-minValue) / step), 255), 0);
        buckets[index].push_back(el);
    }

    vector<int> result;
    for (auto & bucket : buckets){
        if (bucket.size() == numbers.size()){
            // sort(bucket.begin(), bucket.end());
            goto push_elem;
        }

        akySort(bucket);

        push_elem:
        for (auto & el : bucket){
            result.push_back(el);
        }
    }
    numbers = result;
}

int main() {
    int n = 1e5;
    //fin >> n;
    initialNumbers.resize(n);
    for (auto &el : initialNumbers){
        //fin >> el;
        el = rand();
    }
    akySort(initialNumbers);
    cout << is_sorted(initialNumbers.begin(), initialNumbers.end());
//    for (auto &el : initialNumbers){
//        fout << el << " ";
//    }
    return 0;
}