#include "prize.h"
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;
vector<int> asked[200000];
vector<int> Ask(int i){
if(asked[i].empty()) asked[i] = ask(i);
return asked[i];
}
int ans = -1, mx = 0;
int Ask_cnt(int i){
auto v = Ask(i);
if(v[0]+v[1] == 0) ans = i;
return v[0]+v[1];
}
void solve(int l, int r){
if(ans != -1) return;
while(Ask_cnt(l) < mx && l <= r) l++;
if(ans != -1) return;
while(Ask_cnt(r) < mx && r >= l) r--;
if(ans != -1) return;
if(l >= r) return;
auto a = Ask(l), b = Ask(r);
if(a[0] == b[0] && a[1] == b[1]) return;
int md = (l+r)/2;
solve(l, md);
solve(md+1, r);
}
int find_best(int n){
for(int i = 0; i < min(n, 480); i++){
auto v = Ask(i);
mx = max(mx, v[0]+v[1]);
}
solve(0, n-1);
return ans;
}
