#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
#define NL "\n"
#define EL cout << NL
#define FOR(i,n) for (long long i = 0; i < (n); i++)
#define FORS(i,s,n) for (long long i = (s); i < (n); i++)
#define FORR(i,n) for (long long i = (n)-1; i >= 0; i--)
#define PRINTV(v) for (auto a: v) {cout << a << " ";} EL;
#define PRINTVV(v) for (auto a: v) {PRINTV(v);}
#define f first
#define s second
#define all(v) (v).begin(),(v).end()
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll,ll> pl;
typedef vector<pl> vpl;
typedef vector<vpl> vvpl;
vector<vector<int>> cache;
vector<int> askc(ll i) {
if (cache[i][0] != -1) return cache[i];
else return cache[i] = ask(i);
}
vl find_all(ll x, ll y, ll fullcount) {
vl ans;
if (x > y) return {};
auto a1 = askc(x);
auto a2 = askc(y);
if (a1[0]+a1[1] < fullcount) {
ans.push_back(x);
for (auto k: find_all(x+1,y,fullcount)) ans.push_back(k);
return ans;
}
if (a2[0]+a2[1] < fullcount) {
ans.push_back(y);
for (auto k: find_all(x,y-1,fullcount)) ans.push_back(k);
return ans;
}
if (a1[0] == a2[0]) return {};
ll l = x;
ll r = y+1;
while (l+1 < r) {
ll m = (l+r)/2;
auto re = askc(m);
if (re[0]+re[1] < fullcount) {
l = m;
break;
}
if (re[0] > a1[0]) r = m;
else l = m;
}
ans.push_back(l);
for (auto k: find_all(x,l-1,fullcount)) ans.push_back(k);
for (auto k: find_all(l+1,y,fullcount)) ans.push_back(k);
return ans;
}
int find_best(int n) {
ll block = 1;
while (block*block < n) block++;
if (block*block >= n) block--;
assert(block*block < n);
FOR(i,n) cache.push_back({-1,-1});
ll fullcount = 0;
vl indices;
vl lcounts;
vl fcounts;
ll cur = 0;
ll ans = -1;
while (cur < n) {
auto re = askc(cur);
indices.push_back(cur);
lcounts.push_back(re[0]);
fcounts.push_back(re[0]+re[1]);
fullcount = max(fullcount,fcounts.back());
cur += block;
}
fcounts[0] = fullcount;
if (indices.back() != n-1) indices.push_back(n-1);
fcounts.push_back(fullcount);
lcounts.push_back(fullcount);
ll pi = -1;
FOR(i,(ll)indices.size()) {
if (fcounts[i] == -1) continue;
if (pi == -1) {
pi = i;
continue;
}
ll x = indices[pi];
ll y = indices[i];
for (auto k: find_all(x,y,fullcount)) {
auto a = askc(k);
if (a[0] + a[1] == 0) {
ans = k;
break;
}
}
pi = i;
if (ans != -1) break;
}
assert(ans != -1);
auto a = askc(ans);
assert(a[0]+a[1] == 0);
// if (ans == -1) {
// FOR(i,n) {
// if (cache[i][0]+cache[i][1] == 0) ans = i;
// }
// }
return ans;
}
