#include <bits/stdc++.h>
#include "prize.h"
using namespace std;
vector<int> dp[200000];
vector<int> myAsk(int n) {
if(dp[n][0] == -1) dp[n] = ask(n);
return dp[n];
}
int find_best(int n) {
for(int i = 0; i < n; i++) {
dp[i] = {-1, -1};
}
//binary search the first element each time
int hi = 0;
int last = 0;
auto a = myAsk(0);
if (a[0] + a[1] == 0) return 0;
int datMax = a[0] + a[1];
int thatAreMax = 1;
while (true) {
int i1 = last;
int i2 = n - 1;
while (i1 != i2) {
int middle = ceil(((double)i1 + i2) / 2.0);
auto a = myAsk(middle);
if (a[0] + a[1] == 0) return middle;
if(a[0] + a[1] > datMax) {
datMax = a[0] + a[1];
hi += thatAreMax;
thatAreMax = 0;
}
if(i2-i1 > 1) {
if (a[0] - hi == 0) {
if(a[0] + a[1] < datMax) {
i1 = middle;
i2 = middle;
}else i1 = middle+1;
}else {
i2 = middle;
}
}else {
auto b = myAsk(i1);
if(b[0]+b[1] < a[0]+a[1]) {
i2 = i1;
}else i1 = i2;
}
}
auto a = myAsk(i1);
if (a[0] + a[1] == 0) return i1;
last = i1;
if(a[0] + a[1] > datMax) {
datMax = a[0] + a[1];
hi += thatAreMax;
thatAreMax = 0;
}
if (a[0] + a[1] < datMax) hi++;
else thatAreMax++;
}
}
