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

#define N 1000

int count;

bool cmp1(int a, int b)
{
    ++count;
    return a < b;
}

bool cmp2(int a, int b)
{
    ++count;
    return a > b;
}

int main()
{
	std::vector<int> v;
	
	for (int i = 0; i < N; ++i)
		v.push_back(i);

	for (int i = 0; i < 5; ++i) {
		count = 0;
		std::stable_sort(v.begin(), v.end(), i%2 ? cmp2 : cmp1);
		std::cout << "sort " << i + 1 << " count: " << count << std::endl;
	}

	return 0;
}