#include "prize.h"
#include <bits/stdc++.h>
#define maxn 200005
using namespace std;
int N;
int st[4*maxn];
constexpr int B = 474;
inline constexpr int csk(const int &u) {return u/B;}
inline constexpr int csd(const int &u) {return u*B;}
inline constexpr int csc(const int &u) {return min(N, (u+1)*B);}
void upd(int u, int d, int r = 1, int lo = 0, int hi = N-1) {
if (lo == hi) {
st[r] = d;
return;
}
int mid = (lo + hi) >> 1;
if (u <= mid) upd(u, d, r<<1, lo, mid);
else upd(u, d, r<<1|1, mid+1, hi);
st[r] = st[r<<1] + st[r<<1|1];
}
int get(int u, int v, int r = 1, int lo = 0, int hi = N-1) {
if (u > hi || v < lo) return 0;
if (u <= lo && hi <= v) return st[r];
int mid = (lo + hi) >> 1;
return get(u, v, r<<1, lo, mid) + get(u, v, r<<1|1, mid+1, hi);
}
int it[4*maxn];
void build(int r = 1, int lo = 0, int hi = N-1) {
it[r] = hi-lo+1;
if (lo == hi) return;
int mid = (lo + hi) >> 1;
build(r<<1, lo, mid);
build(r<<1|1, mid+1, hi);
}
void update(int u, int d, int r = 1, int lo = 0, int hi = N-1) {
if (lo == hi) {
it[r] = d;
return;
}
int mid = (lo + hi) >> 1;
if (u <= mid) update(u, d, r<<1, lo, mid);
else update(u, d, r<<1|1, mid+1, hi);
it[r] = it[r<<1] + it[r<<1|1];
}
int bfind(int k, int r = 1, int lo = 0, int hi = N-1) {
if (lo == hi) return lo;
int mid = (lo + hi) >> 1, trai = it[r<<1];
if (trai >= k) return bfind(k, r<<1, lo, mid);
return bfind(k-trai, r<<1|1, mid+1, hi);
}
int get_sum(int u, int v, int r = 1, int lo = 0, int hi = N-1) {
if (u > hi || v < lo) return 0;
if (u <= lo && hi <= v) return it[r];
int mid = (lo + hi) >> 1;
return get_sum(u, v, r<<1, lo, mid) + get_sum(u, v, r<<1|1, mid+1, hi);
}
int find_best(int n) {
N = n;
for (int i = 1; i <= 4*N; i++) st[i] = 0;
build();
int num = 0;
vector<int> nho;
for (int i = 0; i < min(474, N); i++) {
vector<int> res = ask(i);
int Prz = (res[0]+res[1]);
if ((Prz+1LL*Prz*Prz+1) > N) {
nho.emplace_back(Prz);
break;
}
if (res[0] + res[1] == 0) return i;
nho.emplace_back(res[0]+res[1]);
}
int p = max_element(nho.begin(), nho.end()) - nho.begin();
for (int i = 0; i < p; i++) {
upd(i, 1);
update(i, 0);
}
vector<int> Old = ask(p);
for (int i = p+1; i < csc(csk(p)); i++) {
vector<int> res = ask(i);
if (res[0] + res[1] == 0) return i;
if (res[0] + res[1] != nho[p]) {
update(i, 0);
upd(i, 1);
}
}
function<int(int)> Fixed = [&](int z) {
return max(z, p+1);
};
for (int o = csk(p); o <= csk(n-1); o++) {
int P = csc(o)-1, Need = 0;
while (P >= Fixed(csd(o))) {
vector<int> Tn = ask(P);
if (Tn[0] + Tn[1] == 0) return P;
if (Tn[0] + Tn[1] != nho[p]) {
update(P, 0);
upd(P, 1);
--P;
continue;
}
Need = Old[1] - Tn[1] - get(p, P);
break;
}
if (P < Fixed(csd(o))) continue;
while (Need--) {
int lo = get_sum(p, Fixed(csd(o))-1)+1, hi = get_sum(p, csc(o)-1);
while (hi != lo) {
int mid = (lo + hi) >> 1,
pos = bfind(mid);
vector<int> res = ask(pos);
if (res[0] + res[1] == 0) return pos;
if (res[0] + res[1] != nho[p]) {
update(pos, 0);
upd(pos, 1);
break;
}
int How_many = Old[1] - res[1] - get(p, pos);
if (How_many) hi = mid-1;
else lo = mid+1;
}
if (lo != hi) continue;
int pos = bfind(lo);
vector<int> H = ask(pos);
if (H[0] + H[1] == 0) return pos;
update(pos, 0);
upd(pos, 1);
}
}
return 0;
}
//10000 queries
//
//5 different gifts
