#include<bits/stdc++.h>
#include "minerals.h"
using namespace std;
typedef vector <int> vi;
const int MAXN = 45000;
int n, prosli = 0;
int dp[MAXN], opt[MAXN];
int calc (int len) {
if (dp[len] != -1) return dp[len];
if (len == 1) return dp[len] = 0;
int res = 1e9;
int x = (double) len / 2.618;
for (int j = 0; j <= 1; j++) {
int i = x + j;
if (i < 1 || i >= len) continue;
int tmp = min(i, len - i) + len - 1 + calc(i) + calc(len - i);
if (tmp < res) {
res = tmp;
opt[len] = i;
}
}
return dp[len] = res;
}
bool pitaj (int x) {
int novi = Query(x);
bool res = (prosli != novi);
prosli = novi;
return res;
}
void calc (vi a, vi b, bool flg) {
int siz = a.size();
if (siz == 1) {
Answer(a[0], b[0]);
return;
}
int x = opt[siz];
vi a1, b1, a2, b2;
for (int i = 0; i < siz; i++) {
if (i < x) {
pitaj(a[i]);
a1.push_back(a[i]);
} else {
a2.push_back(a[i]);
}
}
for (int i = 0; i < siz; i++) {
if (pitaj(b[i]) ^ flg) b2.push_back(b[i]); else b1.push_back(b[i]);
}
calc(a1, b1, !flg);
calc(a2, b2, flg);
}
void init () {
vi a, b;
for (int i = 1; i <= 2 * n; i++) {
if (pitaj(i)) a.push_back(i); else b.push_back(i);
}
calc(a, b, 1);
}
void Solve (int N) {
n = N;
memset(dp, -1, sizeof dp);
calc(n);
init();
}
