#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
const int S = 500;
vector<vector<int>> a;
int ans, mx;
vector<int> query(int i) {
if (a[i].size()) return a[i];
return a[i] = ask(i);
}
void solve(int l, int r) {
if (l > r) return;
int m = (l + r) >> 1;
while (m > l) {
auto g = query(m);
if (g[0] + g[1] == 0) ans = m;
if (g[0] + g[1] == mx) {
int tot = query(m)[0] - query(l)[0];
if (tot) solve(l, m);
break;
}
m--;
}
m = (l + r) >> 1;
m++;
while (m < r) {
auto g = query(m);
if (g[0] + g[1] == 0) ans = m;
if (g[0] + g[1] == mx) {
int tot = query(m)[0] - query(l)[0];
if (tot) solve(l, m);
break;
}
m++;
}
}
int find_best(int n) {
a.resize(n);
if (n <= 5000) {
for (int i = 0; i < n; i++) {
auto g = query(i);
if (g[0] + g[1] == 0) return i;
}
}
int who = 0;
for (int i = 0; i < S; i++) {
auto g = query(i);
if (mx < g[0] + g[1]) {
mx = g[0] + g[1];
who = i;
}
if (1LL * (g[0] + g[1]) * (g[0] + g[1]) > n) {
who = i;
break;
}
if (g[0] + g[1] == 0) {
return i;
}
}
int r = n - 1;
while (r >= who) {
auto g = query(r);
if (g[0] + g[1] == 0) return r;
if (g[0] + g[1] == mx) break;
r--;
}
solve(who, r);
return ans;
}
