#include "prize.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define mk make_pair
#define pb push_back
#define fr first
#define sc second
int lolipop;
vector<pii> resp;
int a(int x) {
if(resp[x].fr != -1) return resp[x].fr;
vector<int> aux = ask(x);
resp[x] = {aux[0], aux[1]};
return resp[x].fr;
}
int b(int x) {
if(resp[x].sc != -1) return resp[x].sc;
vector<int> aux = ask(x);
resp[x] = {aux[0], aux[1]};
return resp[x].sc;
}
int query(int l, int r) {
while(l < r and a(l) + b(l) != lolipop) {
if(a(l) + b(l) == 0) return l;
l++;
}
while(l < r and a(r) + b(r) != lolipop) {
if(a(r) + b(r) == 0) return r;
r--;
}
if(l > r or a(l) == a(r)) return -1; // checo se o intervalo é valido e se existe um valor diferente de lolipop nele
int mid = (l+r)/2;
return max(query(l,mid), query(mid+1,r));
}
int find_best(int n) {
resp.resize(n, mk(-1,-1));
for(int i = 0; i < min(500,n); i++) lolipop = max(lolipop, a(i) + b(i));
return query(0, n-1);
}
