#include "fun.h"
#include <bits/stdc++.h>
#include <vector>
using namespace std;
const int MAXN = 100005;
bool used[MAXN];
int m[MAXN];
int n;
int dfs(int i, int d){
if (2 * i + 1 >= n) {m[i] = d; return d;}
m[i] = dfs(2 * i + 1, d + 1);
if (2 * i + 2 < n) dfs(2 * i + 2, d + 1);
return m[i];
}
int find_deepest(int i){
if (2 * i + 1 >= n) {used[i] = true, m[i]--; return i;}
int res = m[i];
if (!used[2 * i + 1] and !used[2 * i + 2]){
if (m[2 * i + 1] >= m[2 * i + 2])
res = find_deepest(2 * i + 1);
else
res = find_deepest(2 * i + 2);
m[i] = max(m[2 * i + 1], m[2 * i + 2]);
return res;
}
if (used[2 * i + 1] and !used[2 * i + 2]){
res = find_deepest(2 * i + 2);
m[i] = max(m[2 * i + 1], m[2 * i + 2]);
return res;
}
if (!used[2 * i + 1] and used[2 * i + 2])
{
res = find_deepest(2 * i + 1);
m[i] = max(m[2 * i + 1], m[2 * i + 2]);
return res;
}
used[i] = true, m[i]--;
return i;
}
std::vector<int> createFunTour(int N, int Q) {
if (n == 2) return {0, 1};
n = N;
vector<int> res;
dfs(0, 0);
int curr = 0, r, l;
for (int i = 0; i <= n; i += 2){
r = -1;
if (used[2 * curr + 2])
r = curr, curr = 2 * curr + 1;
if (r == -1) r = find_deepest(2 * curr + 2);
l = (used[2 * curr + 1]) ? curr : find_deepest(curr);
if (l == curr)
res.push_back(r);
else
res.push_back(l), res.push_back(r);
}
res.push_back(curr);
return res;
}
