#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;
int l1 = l, r1 = m, l2 = m + 1, r2 = r;
while(r1 > l1) {
get(r1);
if(did[r1].ff + did[r1].ss == 0) return r1;
else if(did[r1].ff + did[r1].ss < mx) r1--;
else break;
}
while(l2 < r2) {
get(l2);
if(did[l2].ff + did[l2].ss == 0) return l2;
else if(did[l2].ff + did[l2].ss < mx) l2++;
else break;
}
int gg = (did[l1].ff == did[r1].ff && did[l1].ss == did[r1].ss ? -1 : solve(l1, r1));
if(gg == -1 && did[l2].ff != did[r2].ff && did[l2].ss != did[r2].ss) gg = solve(l2, r2);
return gg;
}
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 < 478; i++) {
get(i);
if(did[i].ff + did[i].ss > mx) {
mx = did[i].ff + did[i].ss;
l = i;
} else if(did[i].ff + did[i].ss == 0) {
return i;
}
}
while(r > l) {
get(r);
if(did[r].ff + did[r].ss == 0) return r;
else if(did[r].ff + did[r].ss < mx) r--;
else break;
}
return solve(l, r);
}
