#include "machine.h"
#include <bits/stdc++.h>
#define ll long long
#define endl "\n"
using namespace std;
vector<int> generate_unbalanced_sequence(int n) {
if (n % 2 != 0) {
throw invalid_argument("n must be even");
}
vector<int> base(n);
iota(base.begin(), base.end(), 0);
auto bit_counts = [&](const vector<int>& arr) {
int maxv = 0;
for (int x : arr) maxv = max(maxv, x);
int bits = maxv > 0 ? 32 - __builtin_clz(maxv) : 1;
vector<int> cnt(bits, 0);
for (int x : arr) {
for (int k = 0; k < bits; k++) {
if (x & (1 << k)) cnt[k]++;
}
}
return cnt;
};
auto is_unbalanced = [&](const vector<int>& arr) {
int half = arr.size() / 2;
auto cnt = bit_counts(arr);
for (int c : cnt) {
if (c == half) return false;
}
return true;
};
for (int j = n; j <= n + 2; j++) {
for (int rm = 0; rm < n; rm++) {
vector<int> A;
A.reserve(n);
for (int x : base) if (x != rm) A.push_back(x);
A.push_back(j);
if (is_unbalanced(A)) return A;
}
}
throw runtime_error("Failed to generate unbalanced sequence");
}
std::vector<int> find_permutation(int n)
{
std::vector<int> a(n);
for (ll i = 0; i < n; i++)
a[i] = i;
if (!(n & 1))
a = generate_unbalanced_sequence(n);
ll ind[n + 3];
for (ll i = 0; i < n; i++) ind[a[i]] = i;
vector<int> b = use_machine(a);
for (ll bit = 0; bit < 30; bit++)
{
ll cnt1 = 0;
for (ll i = 0; i < n; i++) cnt1 += (a[i] >> bit & 1) - (b[i] >> bit & 1);
if (cnt1)
for (ll i = 0; i < n; i++) b[i] ^= (1 << bit);
}
for (ll i = 0; i < n; i++) b[i] = ind[b[i]];
return b;
}
