#include "minerals.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define ff first
#define sd second
const int mxN = 1e5 + 5;
static ll n,cntt = 0,last = 0;
bool vis[mxN],vis1[mxN];
ll query(ll i){
cntt++;
ll res = Query(i);
vis[i] = 1 - vis[i];
return res;
}
void Solve(int N){
n = N;
vector<ll> v[2],l(2 * n + 5),r(2 * n + 5);
vector<ll> vv(2 * n);
iota(vv.begin(), vv.end(), 1);
random_device rd;
mt19937_64 gen(rd());
uniform_int_distribution<ll> dis(0, 2 * n - 1);
for(int i = 0; i < 2 * n; i++) swap(vv[i], vv[dis(gen)]);
for(int i = 0; i <= 2 * n; i++){
l[i] = -1;
r[i] = n - 1;
}
for(auto i : vv){
if(v[0].size() == n){
v[1].pb(i);
continue;
}
ll res = query(i);
if(res == last){
v[1].pb(i);
l[i] = -1;
ll sz = v[0].size();
r[i] = sz - 1;
}
else v[0].pb(i);
last = res;
}
vector<vector<ll>> q(n + 5);
for(auto i : v[1]){
ll mid = l[i] + (r[i] - l[i]) / 2;
if(r[i] > l[i] + 1) q[mid].pb(i);
else vis1[r[i]] = true;
}
ll op = 0,cnt = n;
while(cnt){
if(op){
for(int j = 0; j < n; j++){
if(!vis1[j]) last = query(v[0][j]);
for(auto i : q[j]){
ll res = query(i);
if(res == last) r[i] = j;
else l[i] = j;
last = res;
if(r[i] <= l[i]){
vis1[r[i]] = true;
continue;
}
while(vis1[r[i]]) r[i]--;
while(vis1[l[i] + 1]) l[i]++;
ll cnt = 0,mid;
for(int ii = l[i] + 1; ii <= r[i]; ii++) cnt += !vis1[ii];
cnt = (cnt + 1) / 2;
for(int ii = l[i] + 1; ii <= r[i]; ii++){
cnt -= !vis1[ii];
if(!cnt){
mid = ii;
break;
}
}
assert(!vis1[mid] and !vis1[l[i] + 1] and !vis1[r[i]]);
// mid = r[i] - (r[i] - l[i]) / 2;
if(r[i] > l[i] + 1){
q[mid].pb(i);
}
else vis1[r[i]] = true;
}
q[j].clear();
}
}
else{
for(int j = n - 1; j >= 0; j--){
for(auto i : q[j]){
ll res = query(i);
if(res == last) r[i] = j;
else l[i] = j;
last = res;
if(r[i] <= l[i]){
vis1[r[i]] = true;
continue;
}
while(vis1[r[i]]) r[i]--;
while(vis1[l[i] + 1]) l[i]++;
// ll mid = l[i] + (r[i] - l[i]) / 2;
ll cnt = 0,mid;
for(int ii = l[i] + 1; ii <= r[i]; ii++) cnt += !vis1[ii];
cnt = (cnt + 1) / 2;
for(int ii = l[i] + 1; ii <= r[i]; ii++){
cnt -= !vis1[ii];
if(!cnt){
mid = ii;
break;
}
}
// mid = r[i] - (r[i] - l[i]) / 2;
if(r[i] > l[i] + 1) q[mid].pb(i);
else vis1[r[i]] = true;
}
q[j].clear();
if(!vis1[j]) last = query(v[0][j]);
}
}
op = 1 - op;
cnt = 0;
for(auto i : v[1]){
// cout << i << ' ' << l[i] << ' ' << r[i] << '\n';
if(r[i] > l[i] + 1){
cnt++;
}
}
}
// cout << cntt << " -- " << '\n';
for(auto i : v[1]) Answer(i, v[0][r[i]]);
}
