#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll N;
vector <vector<int>> dp(200005, {-1, -1});
ll sum(ll idx) {
if (dp[idx][0] == -1) dp[idx] = ask(idx);
return dp[idx][0]+dp[idx][1];
}
map<ll, pair<ll, ll>> mp[200005];
ll dnc(ll l, ll r) {
if (l > r) return -1;
ll mid = (l+r)/2;
if (!sum(mid)) return mid;
auto it = mp[sum(mid)].upper_bound(mid);
bool lf = 1, rg = 1;
if (it != mp[sum(mid)].begin()) {
--it;
if (!((*it).second.second-dp[mid][0])) {
lf = 0;
}
++it;
}
if (it != mp[sum(mid)].end()) {
if (!((*it).second.second-dp[mid][0])) {
rg = 0;
}
}
mp[sum(mid)][mid] = {dp[mid][0], dp[mid][1]};
ll ret = -1;
if (lf) ret = max(ret, dnc(l, mid-1));
if (rg) ret = max(ret, dnc(mid+1, r));
return ret;
}
int find_best(int n) {
N = n;
return dnc(0, N-1);
}
