#include <bits/stdc++.h>
#include "minerals.h"
using namespace std;
const int N = 50000 + 5;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int n, ans[N], ptr, cnt;
set<int> cur;
int query(int x){
if(cur.find(x) != cur.end()) cur.erase(x);
else cur.insert(x);
return cnt = Query(x);
}
vector<int> treevec;
struct SegTree{
map<int, vector<int>> tree;
void clear(){
tree.clear();
}
void build(int v = 1, int l = 1, int r = n, bool flag = false){
if(l > r) return;
if(l == r) ans[l] = tree[v].front();
else{
int m = l + (r - l) * 0.373;
for(int i = l; i <= m; i++) query(treevec[i - 1]);
for(auto x : tree[v]){
if(tree[v * 2].size() == (m - l + 1)) tree[v * 2 + 1].push_back(x);
else if(tree[v * 2 + 1].size() == (r - (m + 1) + 1)) tree[v * 2].push_back(x);
else{
if(cur.find(x) == cur.end()){
int prevcnt = cnt;
query(x);
if(prevcnt + 1 == cnt) tree[v * 2 + flag].push_back(x);
else tree[v * 2 + !flag].push_back(x);
}
else{
int prevcnt = cnt;
query(x);
if(prevcnt == cnt) tree[v * 2 + !flag].push_back(x);
else tree[v * 2 + flag].push_back(x);
}
}
}
build(v * 2, l, m, !flag);
build(v * 2 + 1, m + 1, r, flag);
}
}
};
SegTree sgt;
void Solve(int N_) {
n = N_;
vector<int> tmp, a, b, c1, c2;
vector<int> v(n * 2);
iota(v.begin(), v.end(), 1);
for(int i = 0; i < n; i++){
int prvcnt = cnt;
query(v[i]);
if(cnt == prvcnt + 1) tmp.push_back(v[i]);
else a.push_back(v[i]);
}
while(!tmp.empty()){
int prvcnt = cnt;
query(tmp.back());
if(cnt == prvcnt - 1) c1.push_back(tmp.back());
else b.push_back(tmp.back());
tmp.pop_back();
}
treevec = b;
for(auto x : a) sgt.tree[1].push_back(x);
sgt.build(1, 1, a.size(), true);
for(int i = 1; i <= a.size(); i++) Answer(treevec[i - 1], ans[i]);
a.clear(), b.clear();
for(int i = n; i < n * 2; i++){
int prvcnt = cnt;
query(v[i]);
if(cnt == prvcnt + 1) tmp.push_back(v[i]);
else a.push_back(v[i]);
}
while(!tmp.empty()){
int prvcnt = cnt;
query(tmp.back());
if(cnt == prvcnt - 1) c2.push_back(tmp.back());
else b.push_back(tmp.back());
tmp.pop_back();
}
treevec = b;
sgt.clear();
for(auto x : a) sgt.tree[1].push_back(x);
sgt.build(1, 1, a.size(), true);
for(int i = 1; i <= a.size(); i++) Answer(treevec[i - 1], ans[i]);
treevec = c1;
sgt.clear();
for(auto x : c2) sgt.tree[1].push_back(x);
sgt.build(1, 1, c1.size(), true);
for(int i = 1; i <= c1.size(); i++) Answer(treevec[i - 1], ans[i]);
}
