#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
pair<int, int> pr[200100];
bool used[200100];
pair<int, int> myask(int pos){
if (used[pos]){
return pr[pos];
}
used[pos] = 1;
vector <int> vec = ask(pos);
return pr[pos] = {vec[0], vec[1]};
}
int find_best(int n) {
int mx = -1;
int mxpos = 0;
for (int i = 0; i < min(500, n); i++){
pair<int, int> pr = myask(i);
if (pr.first+pr.second == 0)
return i;
if (pr.first + pr.second > mx){
mx = pr.first + pr.second;
mxpos = i;
}
}
int lst = mxpos;
while(1){
int l = lst+1, r = n;
while(l < r){
int mid = (l+r)>>1;
pair<int, int> pr = myask(mid);
if (pr.first+pr.second == 0)
return mid;
if (pr != myask(lst))
r = mid; else
l = mid+1;
}
lst = l;
while(lst < n){
if (myask(lst).first + myask(lst).second == myask(mxpos).first+myask(mxpos).second)
break;
if (myask(lst).first + myask(lst).second == 0)
return lst;
++lst;
}
}
}
/**
8
3 2 3 1 3 2 3 3
*/
