#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;
int most2 = 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);
dq(mid, right);
}
map<int, int> conv;
set<int> final;
void dq2(int left, int right) { // is there a sus in [conv[left], conv[right]]?
// cout<<"at "<<conv[left]<<", "<<conv[right]<<endl;
if (conv[left] > conv[right])
return;
if (ans[conv[left]].fi == -1)
query(conv[left]);
if (ans[conv[right]].fi == -1)
query(conv[right]);
if (ans[conv[left]].fi + ans[conv[left]].se != most2) {
final.insert(conv[left]);
dq2(left + 1, right);
return;
}
if (ans[conv[right]].fi + ans[conv[right]].se != most2) {
final.insert(conv[right]);
dq2(left, right - 1);
return;
}
if (ans[conv[left]].se == ans[conv[right]].se)
return;
int mid = (left + right) / 2;
dq2(left, mid);
dq2(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, 450); 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;
*/
int counter = 0;
for (int i : pos) {
most2 = max(most2, ans[i].fi + ans[i].se);
conv[counter] = i;
counter++;
}
if (counter == 1) {
return conv[0];
}
dq2(0, pos.size() - 1);
for (int i : final) {
query(i);
if (ans[i].fi + ans[i].se == 0)
return i;
}
return -1;
}
