#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, test;
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<pair<int, int>>> tree;
void clear(){
tree.clear();
}
void build(int v, int l, int r, bool flag){
if(l > r) return;
if(l == r) ans[l] = tree[v].front().second;
else{
// int m = l + (r - l) * 0.385;
int m = l + (r - l) * 0.37;
for(int i = l; i <= m; i++) query(treevec[i]);
// sort(tree[v].begin(), tree[v].end());
shuffle(tree[v].begin(), tree[v].end(), rng);
for(auto p : tree[v]){
if(p.first <= m){
tree[v * 2].push_back(p);
test++;
}
else if(tree[v * 2].size() == (m - l + 1)) tree[v * 2 + 1].push_back(p);
else if(tree[v * 2 + 1].size() == (r - (m + 1) + 1)) tree[v * 2].push_back(p);
else{
if(cur.find(p.second) == cur.end()){
int prevcnt = cnt;
query(p.second);
if(prevcnt + 1 == cnt) tree[v * 2 + flag].push_back(p);
else tree[v * 2 + !flag].push_back(p);
}
else{
int prevcnt = cnt;
query(p.second);
if(prevcnt == cnt) tree[v * 2 + !flag].push_back(p);
else tree[v * 2 + flag].push_back(p);
}
}
}
build(v * 2, l, m, !flag);
build(v * 2 + 1, m + 1, r, flag);
}
}
};
SegTree sgt;
void match(vector<int> a, vector<pair<int, int>> b){
treevec = a;
sgt.clear();
for(auto p : b) sgt.tree[1].push_back(p);
sgt.build(1, 0, (int)a.size() - 1, true);
for(int i = 0; i < a.size(); i++) Answer(treevec[i], ans[i]);
}
void Solve(int N_) {
n = N_;
vector<int> v(n * 2);
iota(v.begin(), v.end(), 1);
shuffle(v.begin(), v.end(), rng);
vector<int> a, c1, c2, indexes;
vector<pair<int, int>> tmp, b;
for(int i = 0; i < n; i++){
int prevcnt = cnt;
query(v[i]);
if(cnt == prevcnt + 1) tmp.push_back({i, v[i]});
else b.push_back({i, v[i]});
}
reverse(tmp.begin(), tmp.end());
while(!tmp.empty()){
pair<int, int> p = tmp.back();
tmp.pop_back();
int prevcnt = cnt;
query(p.second);
if(cnt == prevcnt - 1) c1.push_back(p.second);
else{
a.push_back(p.second);
indexes.push_back(p.first);
}
}
for(auto &p : b) p.first = upper_bound(indexes.begin(), indexes.end(), p.first) - indexes.begin() - 1;
match(a, b);
a.clear(), b.clear(), tmp.clear(), indexes.clear();
for(int i = n; i < n * 2; i++){
int prevcnt = cnt;
query(v[i]);
if(cnt == prevcnt + 1) tmp.push_back({i, v[i]});
else b.push_back({i, v[i]});
}
reverse(tmp.begin(), tmp.end());
while(!tmp.empty()){
pair<int, int> p = tmp.back();
tmp.pop_back();
int prevcnt = cnt;
query(p.second);
if(cnt == prevcnt - 1) c2.push_back(p.second);
else{
a.push_back(p.second);
indexes.push_back(p.first);
}
}
for(auto &p : b) p.first = upper_bound(indexes.begin(), indexes.end(), p.first) - indexes.begin() - 1;
match(a, b);
a = c1;
b.clear();
for(auto x : c2) b.push_back({a.size(), x});
match(a, b);
}
