#include <bits/stdc++.h>
#include "minerals.h"
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int cnt;
set<int> minerals;
int query(int x){
if(minerals.find(x) != minerals.end()) minerals.erase(x);
else minerals.insert(x);
return cnt = Query(x);
}
struct Item{
int x, i;
};
void solve(int l, int r, vector<int> &a, vector<Item> b, bool flag){
if(l > r) return;
else if(l == r) Answer(a[l], b[0].x);
else{
int m = r - (r - l) * 0.375;
vector<Item> lft, rght;
for(int i = m + 1; i <= r; i++) query(a[i]);
for(auto p : b){
if(p.i <= m) lft.push_back(p);
else if(lft.size() == m - l + 1) rght.push_back(p);
else if(rght.size() == r - m) lft.push_back(p);
else if(minerals.find(p.x) == minerals.end()){
int prvcnt = cnt;
query(p.x);
if(flag){
if(cnt == prvcnt + 1) rght.push_back(p);
else lft.push_back(p);
}
else{
if(cnt == prvcnt + 1) lft.push_back(p);
else rght.push_back(p);
}
}
else{
int prvcnt = cnt;
query(p.x);
if(flag){
if(cnt == prvcnt - 1) rght.push_back(p);
else lft.push_back(p);
}
else{
if(cnt == prvcnt - 1) lft.push_back(p);
else rght.push_back(p);
}
}
}
solve(l, m, a, lft, flag);
solve(m + 1, r, a, rght, !flag);
}
}
void Solve(int n) {
vector<int> nums, a, c1, c2, indxs;
vector<Item> tmp, b;
nums.assign(n * 2, 0);
iota(nums.begin(), nums.end(), 1);
shuffle(nums.begin(), nums.end(), rng);
for(int i = 0; i < n; i++){
int prvcnt = cnt;
query(nums[i]);
if(cnt == prvcnt + 1) tmp.push_back({nums[i], i});
else b.push_back({nums[i], i});
}
for(auto p : tmp){
int prvcnt = cnt;
query(p.x);
if(cnt == prvcnt - 1) c1.push_back(p.x);
else{
a.push_back(p.x);
indxs.push_back(p.i);
}
}
for(auto &p : b) p.i = upper_bound(indxs.begin(), indxs.end(), p.i) - indxs.begin() - 1;
solve(0, (int)a.size() - 1, a, b, false);
a.clear(), b.clear(), tmp.clear(), indxs.clear();
for(int i = n; i < 2 * n; i++){
int prvcnt = cnt;
query(nums[i]);
if(cnt == prvcnt + 1) tmp.push_back({nums[i], i});
else b.push_back({nums[i], i});
}
for(auto p : tmp){
int prvcnt = cnt;
query(p.x);
if(cnt == prvcnt - 1) c2.push_back(p.x);
else{
a.push_back(p.x);
indxs.push_back(p.i);
}
}
for(auto &p : b) p.i = upper_bound(indxs.begin(), indxs.end(), p.i) - indxs.begin() - 1;
solve(0, (int)a.size() - 1, a, b, false);
a = c1;
b.clear();
for(auto x : c2) b.push_back({x, (int)a.size()});
solve(0, (int)a.size() - 1, a, b, false);
}
