#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
int N;
ii ans[200005];
set<int> pos;
void query(int n) {
vi res = ask(n);
ans[n] = {res[0], res[1]};
}
int most = 0;
void dq(int left, int right) { // is there a sus in [left, right]?
// cout<<"at "<<left<<", "<<right<<endl;
if (left > right)
return;
if (ans[left].fi == -1)
query(left);
if (ans[right].fi == -1)
query(right);
if (ans[left].fi + ans[left].se != most) {
pos.insert(left);
dq(left + 1, right);
return;
}
if (ans[right].fi + ans[right].se != most) {
pos.insert(right);
dq(left, right - 1);
return;
}
if (ans[left].se == ans[right].se)
return;
int mid = (left + right) / 2;
dq(left, mid - 1);
dq(mid, right);
}
int find_best(int n) {
N = n;
/*
if (N < 10000) {
for (int i = 0; i < N; i++) {
vi res = ask(i);
if (res[0] + res[1] == 0)
return i;
}
return 0;
}
*/
for (int i = 0; i < N; i++) {
ans[i] = {-1, -1};
}
for (int i = 0; i < min(N - 1, 500); i++) {
query(i);
most = max(most, ans[i].fi + ans[i].se);
}
// cout<<"most is "<<most<<endl;
query(0);
query(N - 1);
dq(0, N - 1);
/*
cout<<"pos: ";
for (int i : pos)
cout<<i<<" ";
cout<<endl;
*/
for (int i : pos) {
query(i);
if (ans[i].fi + ans[i].se == 0)
return i;
}
return -1;
}
