#include "minerals.h"
#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
using str = string; // yay python!
#define show(x) cerr << (#x) << " = " << (x) << '\n';
#define output_vector(v) for(auto &x : v){cout << x << ' ';}cout << '\n';
#define output_pairvector(v) for(auto &x : v){cout << x.first << " " << x.second << '\n';}
#define read_vector(v) for(auto &x : v){cin >> x;}
#define vt vector
#define pq priority_queue
#define pb push_back
#define eb emplace_back
#define pii pair<int,int>
#define fir first
#define sec second
#define sz(x) int(x.size())
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define discretize(x) sort(x.begin(), x.end()); x.erase(unique(x.begin(), x.end()), x.end());
const int maxn = 1e5;
set<int> machine;
void dnc(vector<int> a, vector<int> b) {
int n = sz(a); // 2N
if(n == 1) {
// show(a[0]);
// show(b[0]);
Answer(a[0], b[0]);
return;
}
vector<int> a1, b1, a2, b2;
int cnt = 0;
for(auto &A : a)
cnt += (machine.count(A));
for(int i=0; i<n; ++i) {
if(cnt < n/2) {
if(!machine.count(a[i])) { // not in machine, add the left part
Query(a[i]);
machine.insert(a[i]);
++cnt;
}
a1.push_back(a[i]);
} else if(cnt > n/2) {
if(machine.count(a[i])) { // not in machine, add the left part
Query(a[i]);
machine.erase(a[i]);
--cnt;
}
a2.push_back(a[i]);
} else {
if(machine.count(a[i]))
a1.push_back(a[i]);
else
a2.push_back(a[i]);
}
}
Query(1);
int d = Query(1);
for(auto &B : b) {
if(sz(b1) == n/2) {
b2.push_back(B);
continue;
}
if(sz(b2) == n/2) {
b1.push_back(B);
continue;
}
int res = Query(B);
if(!machine.count(B)) {
if(d != res)
b1.push_back(B);
else
b2.push_back(B);
} else {
if(d != res)
b2.push_back(B);
else
b1.push_back(B);
}
d = res;
}
dnc(a1, b1);
dnc(a2, b2);
}
void Solve(int N) {
vector<int> x, y;
int d = 0;
for(int i=1; i<=2*N; ++i) {
int res = Query(i);
if(res > d)
x.push_back(i);
else
y.push_back(i);
d = res;
}
// for(auto &k : machine)
// Query(k);
// machine.clear();
dnc(x, y);
}
