#include "fun.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define all(x) (x).begin(),(x).end()
#define X first
#define Y second
#define sep ' '
#define endl '\n'
#define debug(x) cerr << #x << ": " << x << endl;
const ll MAXN = 1e6 + 10;
const ll INF = 8e18;
const ll MOD = 1e9 + 7; // 998244353; // 1e9 + 9;
struct Node {
int v = 0, b = 0;
Node *l = nullptr, *r = nullptr;
Node(int v) : v(v) { Update(); }
Node(int n, int v) : v(v) {
if ((v << 1) <= n) l = new Node(n, v << 1);
if ((v << 1 | 1) <= n) r = new Node(n, v << 1 | 1);
Update();
}
void Update() {
b = v;
if (l) b = l -> b;
if (r) b = r -> b;
}
int Remove() {
if (!l && !r) return true;
if (l && b == l -> v) l = nullptr;
if (r && b == r -> v) r = nullptr;
if (l && b == l -> b) l -> Remove();
if (r && b == r -> b) r -> Remove();
Update();
return false;
}
};
vector<int> ans;
int n;
void Majik(Node* v) {
if (!v) return;
Node* l = v -> l, *r = v -> r;
if (!l && !r) {
ans.push_back(v -> v);
return;
}
bool L = true;
while (true) {
if (L) {
ans.push_back(l -> b);
if (l -> Remove()) {
if (r) {
ans.push_back(r -> b);
r -> Remove();
}
break;
}
} else {
if (!r) {
Majik(l);
break;
}
ans.push_back(r -> b);
if (r -> Remove()) {
Majik(l);
break;
}
}
L = !L;
}
ans.push_back(v -> v);
}
std::vector<int> createFunTour(int N, int Q) {
n = N;
Node* r = new Node(n, 1);
Majik(r);
for (int& e : ans) e--;
return ans;
}
