#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int find_best(int N) {
int MX = 0, ptr = 0, rg = 0;
vector <vector<int>> dp(N, {-1, -1});
for (int i = 0; i < min(N, 500); i++) {
dp[i] = ask(i);
int Z = dp[i][0]+dp[i][1];
if (!Z) return i;
MX = max(MX, Z);
if (Z == MX) {
ptr = i;
}
}
while (ptr < N) {
if (dp[ptr][0] == -1) dp[ptr] = ask(ptr);
if (MX > dp[ptr][0]+dp[ptr][1]) {
if (!(dp[ptr][0]+dp[ptr][1])) return ptr;
ptr++;
continue;
}
ll lf = ptr+1, rg = N-1, ans = N;
for (;lf <= rg;) {
ll mid = (lf+rg)/2;
if (dp[mid][0] == -1) dp[mid] = ask(mid);
if (!(dp[mid][0]+dp[mid][1])) return mid;
if (dp[mid][1] != dp[ptr][1]) {
ans = mid;
rg = mid-1;
}
else lf = mid+1;
}
ptr = ans;
}
return -1;
}
