#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5e5 + 3e2;
typedef long long ll;
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
int foo, hoo;
vector<int> asked_values[MAXN];
set<int> indexes[MAXN];
void ASK(int i){
vector<int> res;
if (asked_values[i].empty()){
res = ask(i);
//cout << i << ' ' << res.front() << ' ' << res.back() << endl;
} else res = asked_values[i];
foo = res.front();
hoo = res.back();
asked_values[i] = res;
indexes[foo + hoo].insert(i);
}
int get(int i, int r){
ASK(r);
if (*indexes[foo + hoo].begin() == r) return foo;
int l = *prev(indexes[foo + hoo].upper_bound(i));
r = foo;
ASK(l);
l = foo;
return r - l;
}
int find_best(int n) {
int mx = 0;
for (int i = 0; i < min(n, 500); i++){
ASK(i);
if (foo + hoo == 0) return i;
mx = max(mx, foo + hoo);
}
map<int, int> mp;
for (int i = 0; i < n; i++){
int l = i, r = n - 1;
int nxt = n;
while (l <= r){
int m = (l + r) >> 1;
ASK(m);
if (foo + hoo == 0) return m;
if (foo + hoo < mx) nxt = m;
if (get(i, m)){
r = m - 1;
} else l = m + 1;
}
i = nxt;
if (i == n) break;
ASK(i);
for (auto &now : mp){
if (now.first >= foo + hoo) now.second++;
}
if (mp.find(foo + hoo) == mp.end()) mp[foo + hoo] = 1;
}
for (int i = n - 1; i >= n - 200; i--){
if (i < 0) break;
ASK(i);
if (foo + hoo == 0) return i;
}
return n / 2;
}
