#include "minerals.h"
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 43000;
struct Mineral {
int st, dr, mid, id;
} v[2*MAX_N];
int p = 0; // All minerals from 0 to p are added
int lastrez = 0; // Result for minerals from 0 to p
void movePointer(int x) {
while(p < x) {
p++;
lastrez = Query(p);
}
while(p > x) {
lastrez = Query(p);
p--;
}
}
bool hasPair(int x) {
bool frez;
int rez = Query(x);
if(rez == lastrez)
frez = true;
else
frez = false;
Query(x);
return frez;
}
bool lefttoright = false;
bool cmp(Mineral a, Mineral b) {
if(lefttoright)
return a.mid < b.mid;
else
return a.mid > b.mid;
}
void Solve(int N) {
for(int i = 0; i < 2 * N; ++i) {
v[i].st = 0;
v[i].dr = i + 1;
v[i].id = i + 1;
}
int activeQueries = 0;
for(int i = 0; i < 2 * N; ++i) {
if(v[i].dr - v[i].st > 1)
activeQueries++;
v[i].mid = (v[i].st + v[i].dr) / 2;
}
while(activeQueries > 0) {
sort(v, v + 2 * N, cmp);
lefttoright ^= 1;
for(int i = 0; i < 2 * N; ++i) {
if(v[i].dr - v[i].st > 1) {
movePointer(v[i].mid);
if(hasPair(v[i].id))
v[i].dr = v[i].mid;
else
v[i].st = v[i].mid;
}
}
activeQueries = 0;
for(int i = 0; i < 2 * N; ++i) {
if(v[i].dr - v[i].st > 1)
activeQueries++;
v[i].mid = (v[i].st + v[i].dr) / 2;
}
}
for(int i = 0; i < 2 * N; ++i)
if(v[i].dr != v[i].id)
Answer(v[i].id, v[i].dr);
}
