#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int n , cnt[N];
bool marked[N] , dead[N];
int Sq(int val)
{
for(int i = 1 ; i <= val ; i++) if(i * i >= val)
return i;
return val;
}
int Solve()
{
int Q = 0;
int sq = Sq(n);
int mx = 0;
for(int i = 0 ; i < min(n , sq + 10) ; i++)
{
Q++;
auto now = ask(i);
mx = max(mx , now[0] + now[1]);
}
for(int asd = 0 ; asd < mx ; asd++)
{
vector <int> all;
int tmp = 0;
for(int i = 0 ; i < n ; i++) if(!dead[i])
{
if(marked[i])
tmp++;
else
{
cnt[i] = tmp;
all.push_back(i);
}
}
int low = -1 , high = all.size();
while(high - low > 1)
{
Q++;
int mid = (low + high) >> 1;
int id = all[mid];
auto now = ask(id);
//cout << low << " " << high << " " << mid << endl;
if(now[0] + now[1] != mx)
{
//cout << id << "! " << endl;
marked[id] = true;
break;
}
now[0] -= cnt[id];
if(now[0] != 0)
high = mid;
else
low = mid;
dead[id] = true;
}
}
for(int i = 0 ; i < n ; i++) if(marked[i])
{
Q++;
auto now = ask(i);
if(now[0] + now[1] == 0)
return i;
}
return -1;
}
int find_best(int nn) {
n = nn;
if(n == 1)
return 0;
return Solve();
}
