#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];
}
ll dnc(ll l, ll r) {
if (l > r) return -1;
while (l <= r && sum(l) != sum(r)) {
if (sum(r) < sum(l)) {
if (!sum(r)) return r;
r--;
}
else {
if (!sum(l)) return l;
l++;
}
}
if (l == r) {
if (!sum(l)) return l;
return -1;
}
// cek ada yang berharga ga di segment ini
if (dp[r][0] == -1) dp[r] = ask(r);
if (dp[l][0] == -1) dp[l] = ask(l);
if (!(dp[r][0]-dp[l][0])) return -1;
ll mid = (l+r)/2;
return max(dnc(l, mid-1), dnc(mid, r));
}
int find_best(int n) {
N = n;
return dnc(0, N-1);
}
