#include "prize.h"
#include<bits/stdc++.h>
using namespace std;
#define in insert
#define all(x) x.begin(),x.end()
#define pb push_back
#define eb emplace_back
#define ff first
#define ss second
//#define int long long
typedef long long ll;
typedef vector<int> vi;
typedef set<int> si;
typedef multiset<int> msi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
const int mxn = 2e5 + 10;
pair<int, int> did[mxn];
int mx;
pair<int, int> get(int i) {
if(did[i].ff != -1) return did[i];
auto sus = ask(i);
return did[i] = {sus[0], sus[1]};
}
int solve(int l, int r) {
if(l == r) {
get(l);
if(did[l].ff + did[l].ss == 0) return l;
return -1;
}
int m = (l + r) / 2;
while(l < m) {
get(l);
if(did[l].ff + did[l].ss == 0) return l;
else if(did[l].ff + did[l].ss < mx) l++;
else break;
}
while(r > m + 1) {
get(r);
if(did[r].ff + did[r].ss == 0) return r;
else if(did[r].ff + did[r].ss < mx) r--;
else break;
}
if(did[l].ff + did[l].ss == mx && did[r].ff + did[r].ss == mx && did[l].ss == did[r].ss) return -1;
return max(solve(l, m), solve(m + 1, r));
}
int find_best(int n) {
for(int i = 0; i < n; i++) {
did[i] = {-1, -1};
}
if(n <= 5000) {
for(int i = 0; i < n; i++) {
get(i);
if(did[i].ff + did[i].ss == 0) return i;
}
return -69;
}
int l = 0, r = n - 1;
for(int i = 0; i < 448; i++) {
get(i);
if(did[i].ff + did[i].ss > mx) {
mx = did[i].ff + did[i].ss;
}
}
return solve(l, r);
}
