#include <bits/stdc++.h>
//#include "prize.h"
#define MAX_N 200000
using namespace std;
typedef long long lint;
vector<int> ask(int i);
int N;
int mx;
int rez = -1;
int spec[MAX_N + 1];
vector <int> doAsk(int poz)
{
if(rez != -1)
return {0, 0};
vector <int> a = ask(poz - 1);
if(a[0] + a[1] == 0)
rez = poz;
return a;
}
int px;
int cst, cdr;
bool verif(int poz)
{
if(rez != -1)
return 0;
vector <int> a = doAsk(poz);
if(a[0] + a[1] == mx)
{
cst = a[0];
cdr = a[1];
px = poz;
return 1;
}
spec[poz] = 1;
return 0;
}
void intreaba(int poz)
{
int n = N;
if(rez != -1)
return;
if(verif(poz))
return;
int st = poz - 1;
int dr = poz + 1;
while(st >= 1 || dr <= n)
{
if(st >= 1)
{
if(verif(st))
return;
st --;
}
if(dr <= n)
{
if(verif(dr))
return;
dr ++;
}
}
}
void divide(int st, int dr, int pst, int pdr, int cate)
{
if(rez != -1)
return;
if(st > dr || cate == 0)
return;
//cout << " SUNTEM " << st << " " << dr << " AVEM INSRE ST " << pst << " DR " << pdr << " " << cate << "\n";
if((dr - st + 1) - cate <= 2)
{
for(int i = st; i <= dr; i ++)
{
spec[i] = 1;
doAsk(i);
}
return;
}
int mid = (st + dr) >> 1;
intreaba(mid);
divide(st, px - 1, pst, cdr, cst - pst);
divide(px + 1, dr, cst, pdr, cdr - pdr);
}
int find_best(int n)
{
N = n;
if(n <= 5000)
{
for(int i = 0; i < n; i ++)
{
vector<int> a = ask(i);
if(a[0] + a[1] == 0)
return i;
}
assert(1 == 0);
//return;
}
srand(time(0));
for(int i = 1; i <= 10; i ++)
{
lint poz = 1LL * rand() * rand() % n;
vector <int> a = ask(poz);
if(a[0] + a[1] == 0)
return poz;
mx = max(mx, a[0] + a[1]);
}
divide(1, n, 0, 0, mx);
return rez - 1;
}
