#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
typedef int ll;
typedef pair<ll , ll> ii;
#define ff first
#define ss second
#define pb push_back
#define in insert
const ll Q = 5e3;
int ans = 0;
int god_number = 0;
void find(ll l, ll r, ll L, ll M, ll R){
if(M <= 0 || r < l) return;
ll m = (l + r)/2;
auto v = ask(m);
if(v[0] + v[1] == god_number){
find(l, m-1, L, v[0] - L, v[1]);
find(m+1, r, v[0], v[1] - R, R);
return;
}
if(v[0] + v[1] == 0){
ans = m;
return;
}
ll L1 = l, R1 = m-1; ll c = 1; M--;
while(L1 <= R1 && M){
v = ask(R1);
if(v[0] + v[1] == 0){
ans = R1; return;
}
if(v[0] + v[1] == god_number){
if(L1 <= R1-1){
find(L1, R1-1, L, v[0] - L, v[1]);
}
find(m+1, r, v[0] + c, v[1] - c - R, R);
return;
}
M--;
R1--;
c++;
}
if(!M) return;
find(m+1, r, L + c, M, R);
return;
}
int find_best(int n) {
if(n < Q){
for(ll i = 0; i < n; i++){
auto v = ask(i);
if(v[0] + v[1] == 0) return i;
}
}
vector < ll > c(500, 0);
ll fact = 475;
for(int i = 0; i <= fact; i++){
auto v = ask(i);
if(v[0] + v[1] == 0) return i;
c[i] = v[0] + v[1];
if(c[i] != god_number){
god_number = max(c[i], god_number);
continue;
}
}
ll L = 0;
for(ll i = 0; i <= fact; i++){
if(c[i] != god_number) L++;
}
find(fact + 1, n-1, L , god_number - L, 0);
return ans;
}
