#include <bits/stdc++.h>
#include "prize.h"
using namespace std;
int find_best(int n) {
//binary search the first element each time
int hi = 0;
int last = 0;
auto a = ask(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 = ask(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 (a[0] - hi == 0) {
if(datMax < n-1) {
i1 = middle;
i2 = middle;
}else i1 = middle+1;
}else {
i2 = middle;
}
}
auto a = ask(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++;
}
}
