#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <utility>
#include <set>
#include <cmath>
#include <cstring>
#include "prize.h"
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<ll, ll> ii;
int find_best(int n){
vector<vi> res(n, vi());
int maxi = 0;
for (int i = 0; i < min(500, n); i++){
res[i] = ask(i);
if (res[i][0] + res[i][1] == 0)
return i;
maxi = max(maxi, res[i][0] + res[i][1]);
}
int i = 500;
while(i < n){
if (res[i].size() == 0)
res[i] = ask(i);
if (res[i][0] + res[i][1] == 0)
return i;
if (res[i][0] + res[i][1] == maxi){
int beg = i, end = n - 1;
while(beg < end){
int mid = (beg + end)/2;
if (res[i].size() == 0)
res[mid] = ask(mid);
if (res[mid][0] + res[mid][1] == 0)
return mid;
if (res[mid][0] + res[mid][1] < maxi)
end = mid;
else{
if (res[i][1] - res[mid][1] > 0)
end = mid - 1;
else
beg = mid + 1;
}
}
i = beg + 1;
}
else
i++;
}
return i;
}
