#include <bits/stdc++.h>
#include "prize.h"
using namespace std;
#define ll long long
#define eb emplace_back
#define pb push_back
#define fi first
#define se second
#define ii pair<int,int>
#define ve vector
#define all(x) x.begin(), x.end()
#define fo(i,a,b) for (int i=(a); i<=(b); ++i)
#define fd(i,a,b) for (int i=(a); i>=(b); --i)
#define popcount(x) __builtin_popcountll(x)
#define maxi(a, b) a = max(a, b)
#define mini(a, b) a = min(a, b)
#define siz(x) ((int)(x).size())
#define vi ve<int>
#define _ << ' ' <<
const int N = 1e6+5, inf = 1e9+10, mod = 1e9+7, sq = 447;
map<int, vi> mem;
bool finish = 0;
vi get(int x) {
if (!mem.count(x)) {
mem[x] = ask(x);
if (mem[x] == vi{0, 0}) finish = 1;
}
return mem[x];
}
int tot, len;
void rec(int l, int r) {
if (l > r || finish) return;
if (l == r) {
get(l);
return;
}
int m1 = (l + r) >> 1, m2 = m1;
get(m1);
while (m1 > l && get(m1)[0] + get(m1)[1] < tot) m1--;
if (l < m1 && ((l == 0 && get(m1)[0]) || (l && get(m1)[0] > get(l-1)[0]))) {
rec(l, m1-1);
}
while (m2 < r && get(m2)[0] + get(m2)[1] < tot) m2++;
if (m2 < r && ((r == len - 1 && get(m2)[1]) || (r + 1 < len && get(m2)[1] > get(r+1)[1]))) {
rec(m2+1, r);
}
}
mt19937_64 rng((ll)(new char));
int find_best(int n) {
len = n;
int pos = 0, best = 0;
fo(i,1,min(n,240)) {
int P = rng()%n;
vi ans = get(P);
if (ans[0] + ans[1] > best) {
best = ans[0] + ans[1];
pos = P;
}
}
tot = best;
rec(0, n-1);
fo(i,0,n-1) {
if (mem.count(i) && mem[i][0] + mem[i][1] == 0) {
return i;
}
}
assert(0);
}
//void sol() {
//
//}
//
//signed main(){
// ios::sync_with_stdio(0); cin.tie(0);
// if(fopen("A.inp","r")) {
// freopen("A.inp","r",stdin);
// freopen("A.out","w",stdout);
// }
// int tc = 1; // cin >> tc;
// fo(i,1,tc) sol();
// return 0;
//}
