#include "perm.h"
#include <cmath>
#include <functional>
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <list>
#include <time.h>
#include <math.h>
#include <random>
#include <deque>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <cassert>
#include <bitset>
#include <sstream>
#include <chrono>
#include <cstring>
#include <numeric>
using namespace std;
typedef long long ll;
int get_nr_bits(ll x)
{
if (x == 0)
{
return 0;
}
assert(x >= 1);
return get_nr_bits(x / 2) + x % 2;
}
vector<int> normalize(vector<int> v)
{
map<int, int> mp;
for (auto& x : v)
{
mp[x] = 0;
}
int y = 0;
for (auto& it : mp)
{
it.second = y++;
}
for (auto& x : v)
{
x = mp[x];
}
return v;
}
vector<int> construct_permutation(ll total)
{
if (total == 1)
{
return normalize({});
}
if (total == 2)
{
return normalize({ 0 });
}
if (total == 3)
{
return normalize({ 1, 0 });
}
assert(total / 4 >= 1);
assert(total >= 4);
vector<int> sol = construct_permutation(total / 4);
const int INF = 10000;
if (total % 4 == 0)
{
sol.push_back(INF);
sol.push_back(INF + 1);
}
if (total % 4 == 1)
{
sol.push_back(INF);
sol.push_back(INF + 1);
sol.push_back(-1);
}
if (total % 4 == 2)
{
sol.push_back(INF);
sol.push_back(-1);
sol.push_back(INF + 1);
}
if (total % 4 == 3)
{
bool is1 = 0, is10 = 0;
for (auto& x : sol)
{
is1 |= (x == 1);
if (x == 0)
{
is10 |= is1;
}
}
if (is10)
{
for (auto& x : sol) x *= 2;
sol.push_back(INF);
sol.push_back(INF + 1);
sol.push_back(3);
}
else
{
sol.push_back(INF);
sol.push_back(-1);
sol.push_back(INF + 1);
sol.push_back(-2);
}
}
return normalize(sol);
}
