#include <algorithm>
#include "random.h"

using namespace std;

struct key_data
{
	bigint key;
	bigint data;
};

static bool cmp(struct key_data &a, struct key_data &b)
{
	return a.data < b.data;	
}

vector<bigint> permutation_gen(bigint n)
{
	vector<struct key_data> L;

	for (bigint i = 0; i < n; i++)
	{
		struct key_data kv;

		kv.key = i;
		kv.data = random_longlong();

		L.push_back(kv);
	}
	
	sort(L.begin(), L.end(), cmp);

	vector<bigint> ret;

	for (bigint i = 0; i < n; i++)
		ret.push_back(L.at(i).key);

	return ret;
}