#ifndef Chai
#include "prize.h"
#endif
#ifdef Chai
#include "grader.cpp"
#endif
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define pb push_back
#define mp make_pair
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector< ii > vii;
typedef long long LL;
int lim = 472;
vi res[200005];
int best;
int solve(int a, int b, int five, int fivestoleft, int fivestoright)
{
if(five == 0)
{
for(int i = b; i>= a; i--)
{
res[i] = ask(i);
if(res[i][0]+res[i][1] == 0) return i;
}
return -1;
}
if(five == b-a+1) return -1;
if(a> b) return -1;
int M = (a+b)/2;
int locate = -1;
res[M] = ask(M);
if(res[M][0]+res[M][1] == 0) return M;
if(res[M][0]+res[M][1] == best) locate = M;
int zone_left, zone_right;
zone_left = zone_right = M;
for(int i = 1; locate==-1; i++)
{
res[M-i] = ask(M-i);
if(res[M-i][0]+res[M-i][1] == 0) return M-i;
if(res[M-i][0]+res[M-i][1] == best)
{
locate = M-i;
break;
}
zone_left = M-i;
res[M+i] = ask(M+i);
if(res[M+i][0]+res[M+i][1] == 0) return M+i;
if(res[M+i][0]+res[M+i][1] == best)
{
locate = M+i;
break;
}
zone_right = M+i;
}
assert(locate != -1);
int ans1;
int Left = res[locate][0], Right = res[locate][1];
if(locate> M)
{
int szL = zone_left-a;
int szR = b-locate;
int fL = szL-(Left-fivestoleft);
int fR = szR-(Right-fivestoright);
int nfL = szL-fL;
int nfR = szR-fR;
ans1 = solve(a, zone_left-1, fL, fivestoleft, nfR+fivestoright);
if(ans1 != -1) return ans1;
return solve(locate+1, b, fR, fivestoleft+nfL, fivestoright);
}
else
{
int szL = locate-a;
int szR = b-zone_right;
int fL = szL-(Left-fivestoleft);
int fR = szR-(Right-fivestoright);
int nfL = szL-fL;
int nfR = szR-fR;
ans1 = solve(a, locate-1, fL, fivestoleft, nfR+fivestoright);
if(ans1 != -1) return ans1;
return solve(zone_right+1, b, fR, fivestoleft+nfL, fivestoright);
}
}
int find_best(int n)
{
best = 0;
int five = 0;
for(int i = 0; i< n; i++) res[i].assign(2, -1);
for(int i = 0; i< lim; i++)
{
vi x = ask(i);
res[i] = x;
if(x[0]+x[1] == 0) return i;
best = max(best, x[0]+x[1]);
}
int left_border = -1, right_border = -1;
for(int i = 0; i< lim; i++)
{
if(res[i][0]+res[i][1] == best)
{
left_border = i;
five++;
}
}
int tot5 = n-best;
int k = solve(left_border+1, n-1, tot5-five, left_border+1-five, 0);
return k;
}
/*
8
3 2 3 1 3 3 2 3
*/
