#include <bits/stdc++.h>
#include "prize.h"
#define pii pair<int,innt>
#define vi vector<int>
#define fi first
#define se second
using namespace std;
typedef long long ll;
const int MAXN = 2e5 + 50;
vi ans[MAXN];
int cur = 0;
int ret = -1;
void solve(int l, int r) {
if (r - l < 2 || ret != -1)
return;
if (ans[l][1] == ans[r][1])
return;
int m = (l + r) / 2;
ans[m] = ask(m);
if (ans[m][0] + ans[m][1] == 0) {
ret = m;
return;
}
if (ans[m][0] + ans[m][1] != cur) {
solve(l, m);
solve(m, r);
return;
}
if (ans[l][0] == ans[m][0] && ans[m][0] == ans[r][0])
return;
if (ans[l][0] == ans[m][0])
solve(m, r);
else if (ans[l][0] == ans[m][0])
solve(l, m);
else {
solve(l, m);
if (ret != -1)
return;
solve(m, r);
}
}
int find_best(int n) {
int val = 454;
for (int i = 0; i < min(n,455); i++) {
ans[i] = ask(i);
if (ans[i][0] + ans[i][1] == 0)
return i;
cur = max(cur, ans[i][0] + ans[i][1]);
if (cur > 100) {
val = i;
break;
}
}
if (val < n - 1)
ans[n-1] = ask(n-1);
if (ans[n-1][0] + ans[n-1][1] == 0)
return n-1;
solve(val,n-1);
return ret;
}
