#include "prize.h"
#include <bits/stdc++.h>
#define maxn 200005
using namespace std;
int N;
int st[2*maxn];
void upd(int u, int d) {
for (st[u+=N+1] = d; u >>= 1;) st[u] = st[u<<1] + st[u<<1|1];
}
int get(int l, int r) {
int res = 0;
for (l += N+1, r += N+2; l < r; l >>= 1, r >>= 1) {
if (l&1) res += st[l++];
if (r&1) res += st[--r];
}
return res;
}
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 find_best(int n) {
N = n;
for (int i = 1; i <= 2*N; i++) st[i] = 0;
build();
vector<int> nho;
for (int i = 0; i < min(500, N); i++) {
vector<int> res = ask(i);
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);
}
int Need = nho[p] - p;
int Number = N-nho[p];
vector<int> Old = ask(p);
int lo = 0, hi = Number;
while (Need--) {
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;
}
}
return 0;
}
//10000 queries
//
//5 different gifts
/*
8
3 2 3 1 3 3 2 3
*/
