/*
	© MATTO MATTI 2018
	http://mattomatti.com/pl/fs18
	napisane przy użyciu Visual Studio Community 2015
	2018-01-18 v 1.0
*/

#include <iostream>
#include <vector>
#include <stack>

using namespace std;

void sortuj(int* dane, int n) {
	vector< stack<int> > v;
	for (int i = 0; i < n; i++) {
		int wybor = 0;
		while (wybor < v.size() && dane[i] > v[wybor].top())
			wybor++;
		if(wybor == v.size())
			v.push_back(stack<int>());
		v[wybor].push(dane[i]);
	}
	for (int i = 0; i < n; i++) {
		int min = 0;
		for (int j = 1; j < v.size(); j++)
			if (v[j].top() < v[min].top())
				min = j;
		dane[i] = v[min].top();
		v[min].pop();
		if (v[min].size() == 0)
			v.erase(v.begin() + min);
	}
}

int main() {
	int n;
	cout << "Podaj ile jest elementow\n n = ";
	cin >> n;
	int* tab = new int[n];
	cout << "Podaj elementy:\n";
	for (int i = 0; i < n; i++)
		cin >> tab[i];
	sortuj(tab, n);
	cout << "Po posortowaniu:\n";
	for (int i = 0; i < n; i++)
		cout << tab[i] << " ";
	system("pause");
	return 0;
}