#include "integer.h"
#include <vector>
#include <random>
#include <numeric>
#include <iostream>
#include <algorithm>
using namespace std;

#define all(x) (x).begin(), (x).end()
#define ssz(x) (int((x).size()))

auto chmax = [](auto& x, auto y) { if (x < y) x = y; };
auto chmin = [](auto& x, auto y) { if (y < x) x = y; };

using ll = long long;

mt19937 rng;
vector<int> findPermutation(int n)
{
	vector<int> ps(n), ans(n);
	iota(all(ps), 0);
	shuffle(all(ps), rng);
	
	for (int i = 0; i < n; i++)
		operate(ps[i]);
	int fn = 0;
	vector<int> nps;
	vector<pair<int, int>> getp, ngtp;
	
	while (!ps.empty())
	{
		int top = n, lgx = -1, lst = n + __builtin_popcount(fn);
		for (int i = 0; i < ssz(ps); i++)
		{
			int x = operate(ps[i]);
			// cerr << x << " " << ps[i] << endl;
			if (x <= lst)
			{
				if (top == n)
				{
					lst -= __builtin_popcount(fn);
					fn++;
					lst += __builtin_popcount(fn);
				}
				else
					lst++;
				ans[ps[i]] = top - (lst - x);
				top -= (lst - x);
				// cerr << "find " << top << endl;
				ngtp.emplace_back(ps[i], top), lgx = ps[i];
			}
			else
				nps.push_back(ps[i]);
			lst = x;
		}
		// cerr << "remake " << top << endl;
		operate(lgx);
		for (auto x : getp)
			if (x.second >= top)
				operate(x.first);
		getp.insert(getp.end(), all(ngtp));
		ngtp.clear();
		// shuffle(all(nps), rng);
		ps = nps;
		nps.clear();
	}
	return ans;
}