#include <bits/stdc++.h>
#include "prize.h"
//#include "Lgrader.cpp"
using namespace std;
template<class T, class T2> inline int chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline int chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
const int MAXN = (1 << 20);
vector<int> memo[MAXN];
int Q = 0;
bool stop;
bool dummy[MAXN];
vector<int> query(int i)
{
if(!memo[i].empty()) return memo[i];
if(stop || dummy[i]) return vector<int>(2, 1e9);
memo[i] = ask(i), Q++;
if(Q == 10000) assert(false);
return memo[i];
}
int n;
mt19937 mt(42);
bool useless(int l, int r)
{
if(query(l)[1] - query(r)[1] == 0) return true;
//if(query(r)[0] - query(l)[0] == 0) return true;
return false;
}
int cnt(int l, int r) { return query(l)[1] - query(r)[1]; }
void rec(int l, int r)
{
if(r < l) return;
int mid = (l + r) >> 1;
if(query(l - 1)[0] + query(l - 1)[1] == 0) stop = 1;
if(query(mid)[0] + query(mid)[1] == 0) stop = 1;
if(query(r + 1)[0] + query(r + 1)[1] == 0) stop = 1;
if(useless(l - 1, r + 1))
{
for(int i = l; i <= r; i++)
memo[i] = query(l - 1);
return;
}
if(cnt(l - 1, mid) > cnt(mid, r + 1))
{
if(useless(l - 1, mid))
for(int i = l; i < mid; i++)
dummy[i] = 1;
else
rec(l, mid - 1);
if(useless(mid, r + 1))
for(int i = mid + 1; i <= r; i++)
dummy[i] = 1;
else
rec(mid + 1, r);
}
else
{
if(useless(mid, r + 1))
for(int i = mid + 1; i <= r; i++)
dummy[i] = 1;
else
rec(mid + 1, r);
if(useless(l - 1, mid))
for(int i = l; i < mid; i++)
dummy[i] = 1;
else
rec(l, mid - 1);
}
}
const int B = 500;
int find_best(int n)
{
::n = n;
if(n < 1000)
rec(1, n - 2);
else
{
int l = 0;
while(l < n)
{
int r = min(n - 1, l + B - 1);
if(!useless(l, r))
rec(l + 1, r - 1);
else
for(int i = l; i <= r; i++)
dummy[i] = 1;
l += B;
}
}
for(int i = 0; i < n; i++)
if(query(i)[0] + query(i)[1] == 0)
return i;
return -1;
}
