#include "minerals.h"
#include <bits/stdc++.h>
using namespace std;
unordered_map<int, int> m;
unordered_map<int, int> unm;
map<pair<int,int>, queue<int>> candidates;
unordered_map<int, bool> ins;
int Q(int i) {
ins[i] = !ins[i];
return Query(m[i]+1);
}
void InitRand(int N) {
srand(7);
vector<int> order(2*N);
for (int i = 0; i < 2*N; i++) order[i]=i;
random_shuffle(order.begin(), order.end());
random_shuffle(order.begin(), order.end());
for (int i = 0; i < 2*N; i++) {
m[i]=order[i];
unm[order[i]]=i;
//m[i] = i;
}
}
pair<int,int> inserted;
vector<int> lefts;
int q = -1;
void prepareInterval(pair<int,int> interval, pair<int, int> full) {
//cout << "Preparing intervals: " << "in - (" << inserted.first << "; " << inserted.second << ") target - (" << interval.first << "; " << interval.second << ")\n";
for (int i = full.first; i <= full.second; i++) {
if (i >= interval.first && i <= interval.second) {
if (!ins[i]) Q(i);
}
else if (ins[i]) Q(i);
}
}
void search(int i, int j,bool thing) {
//cout << "Searching i=" << i << " j=" << j << endl;
if (i == j) return;
int a = i;
int diff = j - i + 1;
int mid;
if (thing) mid = (diff*2)/3;
else mid = (diff+2)/3;
int b = a + mid - 1;
i = b+1;
pair<int, int> full = make_pair(a, j);
pair<int, int> l = make_pair(a, b);
pair<int, int> r = make_pair(i, j);
if (thing) prepareInterval(r, full);
else prepareInterval(l, full);
if (thing) inserted = r;
else inserted = l;
int lcount = b - a + 1;
int rcount = j - i + 1;
while (!candidates[full].empty()) {
int c = candidates[full].front();
candidates[full].pop();
if (lcount == 0) {
candidates[r].push(c);
rcount--;
continue;
}
else if (rcount == 0) {
candidates[l].push(c);
lcount--;
continue;
}
int next = Q(c);
if (thing) {
if (q == next) {
candidates[r].push(c);
rcount--;
}
else {
candidates[l].push(c);
lcount--;
}
}
else {
if (q == next) {
candidates[l].push(c);
lcount--;
}
else {
candidates[r].push(c);
rcount--;
}
}
q = next;
}
search(a, b, true);
search(i, j, false);
}
void Solve(int N) {
InitRand(N);
pair<int,int> interval = make_pair(0, 2*N-1);
for (int i = 0; i < 2*N; i++) {
ins[i] = false;
candidates[interval].push(i);
}
interval = make_pair(0, N-1);
q = Q(0);
lefts.push_back(0);
for (int i = 1; i < 2*N; i++) {
int next = Q(i);
if (q == next) {
candidates[interval].push(i);
}
else {
q = next;
lefts.push_back(i);
}
}
inserted = make_pair(0, N-1);
//cout << "Left: ";
for (auto i : lefts) {
//cout << i << " ";
}
search(0, N-1, true);
for (int i = 0; i < N; i++) {
int a = m[lefts[i]];
int b = m[candidates[make_pair(i, i)].front()];
//cout << a << " = " << b << endl;
Answer(a+1, b+1);
}
}
/*
4
0 4
1 5
2 3
6 7
*/
