#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
#define rep(i, j, k) for (int i = j; i < (int)k; i++)
typedef vector<int> vi;
inline bool smax(int &a, int b) {
if (a < b) {
a = b;
return true;
}
return false;
}
inline bool smin(int &a, int b) {
if (b < a) {
a = b;
return true;
}
return false;
}
map<int, vi> mp;
inline vi gholi(int v) {
if (mp.count(v)) return mp[v];
assert(mp.size() + 1 <= 10000);
return (mp[v] = ask(v));
}
inline int sum(vi me) { return me[0] + me[1]; }
int mx;
int solve(int l, int r, int le, int ri) {
if (l >= r || le + ri == mx) return -1;
int mid = l + r >> 1;
int l2 = mid, r2 = mid, pos = mid;
rep(i, 0, r - l) {
mid += (i & 1) ? -i : i;
smin(l, mid);
smax(r, mid);
pos = mid;
vi me = gholi(mid);
if (sum(me) == 0) return mid;
if (sum(me) == mx) break;
}
if (r2 - l2 + le + ri == mx) return -1;
int res = solve(l, l2, le, pos - l2 + gholi(pos)[1]);
if (~res) return res;
return solve(r2 + 1, r, r2 - pos + gholi(pos)[0], ri);
}
int find_best(int n) {
mp.clear();
mx = -1;
rep(i, 0, min(n, 450)) smax(mx, sum(gholi(i)));
return solve(0, n, 0, 0);
}
