// author : thembululquaUwU
// 3.9.2024
#include <bits/stdc++.h>
#include "minerals.h"
#define pb push_back
#define fi first
#define se second
#define endl '\n'
using namespace std;
using ll = long long;
using ii = pair <int, int>;
using vi = vector <int>;
const int N = 2e5 + 5;
const int mod = 1e9 + 7;
void maxl(auto &a, auto b) {a = max(a, b);}
void minl(auto &a, auto b) {a = min(a, b);}
// grader
//int cnt[N], diff = 0, used[N], c[N], n;
//
//int Query(int id){
// diff -= (cnt[c[id]] > 0);
// if (used[id]) cnt[c[id]] --;
// else cnt[c[id]] ++;
// used[id] ^= 1;
// diff += (cnt[c[id]] > 0);
// return diff;
//}
//
//void Answer(int a, int b){
// cout << a << ' ' << b << endl;
//}
// end
int rt[N], last = 0, q[N], f[N], trace[N];
void dnc(vector <int> p, int L, int R, int op){
if (p.empty()) return;
if (L == R) {
rt[p[0]] = q[L];
return;
}
vector <int> lf, rg;
int mid;
if (!op){
mid = L + trace[R - L + 1] - 1;
for (int i = L; i <= mid; ++ i) last = Query(q[i]);
}
else {
mid = R - trace[R - L + 1];
for (int i = mid + 1; i <= R; ++ i) last = Query(q[i]);
}
for (int id : p){
int _new = Query(id);
if (_new == last) lf.push_back(id);
else rg.push_back(id);
last = _new;
}
dnc(lf, L, mid, 1);
dnc(rg, mid + 1, R, 0);
}
void prepare(int n){
f[1] = 0;
for (int i = 2; i <= n; ++ i){
auto calc = [&](int j) -> int {
return f[j] + f[i - j] + j + i;
};
auto upd = [&](int v, int lst) -> void{
if (f[i] > v){
f[i] = v;
trace[i] = lst;
}
};
int low = 1, high = i / 2;
f[i] = calc(high), trace[i] = high;
while (low <= high){
int mid = low + high >> 1;
int v1 = calc(mid), v2 = calc(mid + 1);
if (v1 > v2){
upd(v2, mid + 1);
low = mid + 1;
}
else {
upd(v1, mid);
high = mid - 1;
}
}
}
}
void Solve(int n){
prepare(n);
vector <int> cur;
int tot = 0, last = 0;
for (int i = 1; i <= n + n; ++ i){
int _new = Query(i);
if (_new == last) q[++ tot] = i;
else cur.push_back(i);
last = _new;
}
for (int i = 1; i <= n + n; ++ i) last = Query(i);
dnc(cur, 1, n, 0);
for (int id : cur) Answer(id, rt[id]);
}
//void solve(){
// cin >> n;
// for (int i = 1; i <= n; ++ i){
// int a, b; cin >> a >> b;
// c[a] = i, c[b] = i;
// }
//
// Solve(n);
//}
//
//int main(){
// if (fopen("pqh.inp", "r")){
// freopen("pqh.inp", "r", stdin);
// freopen("pqh.out", "w", stdout);
// }
// ios_base::sync_with_stdio(0);
// cin.tie(0); cout.tie(0);
//
// int t = 1; // cin >> t;
// while (t --) solve();
// return 0;
//}
