#include <bits/stdc++.h>
#include "prize.h"
using namespace std;
const int MAXN = 2e5+5;
bool vis[MAXN];
pair<int,int> query[MAXN];
int zz = -1;
pair<int,int> req(int i){
if (vis[i]) return query[i];
vector<int> x = ask(i);
pair<int,int> y = {x[0], x[1]};
vis[i] = true;
query[i] = y;
if (y.first + y.second == 0) zz = i;
return y;
}
int gsum(int i){
return req(i).first + req(i).second;
}
int sm = -1;
void getrng(int a, int b){
if (a > b) return;
while ((a <= b) && (gsum(a) != sm)){
a++;
}
if (a >= b) return;
while ((b >= a) && (gsum(b) != sm)){
b--;
}
if (a >= b) return;
auto [l0, r0] = req(a);
auto [l1, r1] = req(b);
if (r0-r1 == 0) return;
while (r0-r1 > 0){
int lo = a+1;
int hi = b-1; //try and find first non-lollipop
while (lo <= hi){
int mid = (lo+hi)/2;
auto [lx, rx] = req(mid);
if (lx + rx != sm){
getrng(a,mid-1);
getrng(mid+1,b);
return;
}
else{
if (r0-rx == 0){
lo = mid+1;
}
else{
hi = mid-1;
}
}
}
//usually id set the next a to be the idx+1 if idx is the non-lollipop, but we should probably cascade well anyways?
//like every guy will be visited and it will returned anyways lmfao??
}
}
const int B = 424;
const int S = 472;
int find_best(int n) {
for (int i = 0; i<=min(n-1,S); i++){
sm = max(sm, gsum(i));
}
int st = S+1;
for (int i = 0; i<B; i++){
if (st == n) break;
int nd = min(n-1, st + S);
getrng(st, nd);
st = nd+1;
}
return zz;
}
