#include "minerals.h"
#include<vector>
using namespace std;
vector<int>L, R;
struct SEG {
vector<int>L;
int l, r, s, e, who, ck;
} seg[212121];
int segN = 1, segW[212121];
void make_seg(int now, int s, int e) {
seg[now].who = s;
seg[now].s = s; seg[now].e = e;
if (s == e) {
segW[s] = now;
return;
}
int m = (s + e) / 2;
if (!seg[now].l)seg[now].l = ++segN;
make_seg(seg[now].l, s, m);
if (!seg[now].r)seg[now].r = ++segN;
make_seg(seg[now].r, m + 1, e);
}
int is_in[212121];
void go_down(int now, int s, int e) {
seg[now].ck = 1;
// printf("%d %d %d\n", now, s, e);
if (s == e || seg[now].L.empty()) {
for (int p : seg[now].L) if (is_in[p])Query(p);
Query(L[s]);
return;
}
int m = (s + e) / 2, l = seg[now].l, r = seg[now].r, bef;
for (int i = m + 1; i <= e; i++)bef = Query(L[i]);
for (int p : seg[now].L) {
int res = Query(p);
is_in[p] = !is_in[p];
if (res == bef) {
seg[l].L.push_back(p);
Query(p);
is_in[p] = !is_in[p];
}
else {
seg[r].L.push_back(p);
Query(p);
is_in[p] = !is_in[p];
}
}
go_down(l, s, m);
}
void Solve(int n) {
int cnt = 0;
for (int i = 1; i <= n * 2; i++) {
int res = Query(i);
if (res != cnt) {
L.push_back(i);
} else {
seg[1].L.push_back(i);
Query(i);
}
cnt = res;
}
make_seg(1, 0, n - 1);
go_down(1, 0, n - 1);
for (int i = 2; i <= segN; i++) {
int s = seg[i].s, e = seg[i].e;
if (seg[i].ck || seg[i].L.empty() || s == e)continue;
for(int j = s; j <= e; j++) Query(L[j]);
go_down(i, s, e);
}
for (int i = 0; i < n; i++) {
for (int p : seg[segW[i]].L) {
Answer(L[i], p);
}
}
}
