#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, a, b) for(int i = (a) - 1; i >= (b); i--)
#define SZ(a) int(a.size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first	
#define S second

typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef double db;

LL cntInv(const VI& a, int l, int r)
{
	LL res = 0;
	FOR(i, l, r)
		FOR(j, i + 1, r)
			if (a[i] > a[j])
				res++;
	return res;
}

mt19937 rng;

int rand(int a, int b)
{
	return a + rng() % (b - a + 1);
}

void solve()
{
	int n = rand(1, 1000);
	vector<int> a(n);
	for (int& x : a)
		x = rand(1, n);
	cout << n << "\n";
	for (int x : a)
		cout << x << " ";
	cout << "\n";
	set<int> used = {-1, n};
	multiset<LL> s = {cntInv(a, 0, n)};
	set<int> unused;
	FOR(i, 0, n)
		unused.insert(i);
	FOR(i, 0, n)
	{
		LL z = *prev(s.end());
		cout << z << " ";
		int k = rand(0, SZ(unused) - 1);
		auto iter = unused.begin();
		while(k--)
		{
			iter++;
			assert(iter != unused.end());
		}
		LL p = *iter;
		cout << ((p + 1) ^ z) << " ";
		auto it = used.lower_bound(p);
		s.erase(s.find(cntInv(a, *prev(it) + 1, *it)));
		s.insert(cntInv(a, *prev(it) + 1, p));
		s.insert(cntInv(a, p + 1, *it));
		used.insert(p);
		unused.erase(iter);
	}
	cout << "\n";
}

int main(int argc, char* argv[])
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	rng.seed(atoi(argv[1]));
	int t = rand(1, 10);
	cout << t << "\n";
	while (t--)
		solve();
	return 0;
}