#include "prize.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ll long long
#define mp make_pair
#define pub push_back
#define pob pop_back()
#define ss second
#define ff first
#define mt make_tuple
#define pof pop_front()
#define fbo find_by_order
#define ook order_of_key
#define lb lower_bound
#define ub upper_bound
typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
using pll = pair <ll, ll>;
using pii = pair <int, int>;
int ans = -1;
void solve(int l, int r, vector <int> resl, vector <int> resr) {
if ( ans != -1 )
return;
if ( resl[0] + resl[1] == 0 ) {
ans = l;
return;
}
if ( resr[0] + resr[1] == 0 ) {
ans = r;
return;
}
if ( l + 1 >= r )
return;
if (resl[0] + resl[1] < resr[0] + resr[1]) {
solve(l + 1, r, ask(l + 1), resr);
return;
}
if (resl[0] + resl[1] > resr[0] + resr[1]) {
solve(l, r - 1, ask(l), ask(r - 1));
return;
}
if ( resl[0] == resr[0] && resl[1] == resr[1] )
return;
int mid = (l + r) / 2;
vector <int> resm = ask(mid);
solve(l, mid, resl, resm);
solve(mid, r, resm, resr);
}
int find_best(int n) {
solve(0, n - 1, ask(0), ask(n - 1));
return ans;
}
