#include "prize.h"
#include<bits/stdc++.h>
using namespace std;
long long lol = 0;
int ans = 0;
int tl = 0,tr;
bool dude(int l, int r, int brl, int brr, int br) {
if(l > tr || r < tl) {
return false;
}
if(br == 0 || l > r) {
return false;
}
if(l == r) {
vector<int> wut = ask(l);
if(wut[0]+wut[1] == 0) {
ans = l;
return true;
}
return false;
}
vector<int> wut(0);
int midl = (l+r)/2+1;
int midr = midl-1;
int p;
for(int i = 0; i < r-l+1; i++) {
if(i%2 == 0) {
midl--;
wut = ask(midl);
p = midl;
}
else {
midr++;
wut = ask(midr);
p = midr;
}
if(wut[0]+wut[1] == 0) {
ans = p;
return true;
}
if(wut[0] == 0) {
tl = max(tl,p+1);
}
if(wut[1] == 0) {
tr = min(tr,p-1);
}
if(wut[0]+wut[1] == lol) {
if(i%2 == 0) {
if(wut[0]-brl > wut[1]-brr-i) {
if(dude(l,midl-1,brl,wut[1],wut[0]-brl)) {
return true;
}
if(dude(midr+1,r,wut[0],brr,wut[1]-brr-i)) {
return true;
}
}
else {
if(dude(midr+1,r,wut[0],brr,wut[1]-brr-i)) {
return true;
}
if(dude(l,midl-1,brl,wut[1],wut[0]-brl)) {
return true;
}
}
}
else {
if(wut[0]-i-brl > wut[1]-brr) {
if(dude(l,midl-1,brl,wut[1],wut[0]-i-brl)) {
return true;
}
if(dude(midr+1,r,wut[0],brr,wut[1]-brr)) {
return true;
}
}
else {
if(dude(midr+1,r,wut[0],brr,wut[1]-brr)) {
return true;
}
if(dude(l,midl-1,brl,wut[1],wut[0]-i-brl)) {
return true;
}
}
}
break;
}
}
return false;
}
int find_best(int n) {
tr = n-1;
int z = 0;
for(int i = 0; i < n; i++) {
vector<int> wut = ask(i);
int c = wut[0]+wut[1];
if(c == 0) {
return i;
}
if(c > lol) {
lol = c;
z = 1;
}
else if(c == lol) {
z++;
}
if(z*z > n || lol*lol*lol*lol > (long long)n) {
break;
}
}
dude(0,n-1,0,0,lol);
return ans;
}
