#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
struct SegmentTree {
vector<int> t;
SegmentTree(int n) {
t = vector<int>(4*n);
}
int get(int v, int tl, int tr, int l, int r) {
if (l > r) return 0;
else if (tl == l && tr == r) return t[v];
else {
int tm = (tl+tr)/2;
return get(2*v, tl, tm, l, min(r, tm))+get(2*v+1, tm+1, tr, max(l, tm+1), r);
}
}
void update(int v, int tl, int tr, int pos) {
if (tl == tr) t[v]++;
else {
int tm = (tl+tr)/2;
if (pos <= tm) update(2*v, tl, tm, pos);
else update(2*v+1, tm+1, tr, pos);
t[v] = t[2*v]+t[2*v+1];
}
}
};
map<int, vector<int>> dp;
vector<int> askDP(int i) {
if (dp.count(i)) return dp[i];
dp[i] = ask(i);
return dp[i];
}
int find_best(int n) {
dp = map<int, vector<int>>();
// While not all are found
int mxNum = 0;
for (int i = 0; i < min(473, n); i++) {
vector<int> ans = askDP(i);
mxNum = max(ans[0]+ans[1]+1, mxNum);
}
SegmentTree tree(n);
vector<int> arr(n);
iota(arr.begin(), arr.end(), 0);
int d = -1;
while (d == -1) {
int lo = 0, hi = arr.size()-1, idx = -1, mid;
while (lo <= hi) {
mid = (lo+hi)/2;
vector<int> ans = askDP(arr[mid]);
if (ans[0] == 0 && ans[1] == 0) {
d = arr[mid];
idx = mid;
break;
} else if (ans[0]+ans[1]+1 != mxNum) {
idx = mid;
break;
} else if (ans[0] > tree.get(1, 0, n-1, 0, arr[mid]-1)) {
hi = mid - 1;
} else
lo = mid + 1;
}
assert(idx != -1);
tree.update(1, 0, n-1, arr[idx]);
// arr.erase(arr.begin()+idx);
}
return d;
}
