#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
struct BIT {
int n;
vector<int> tree;
void init(int n) {
tree.resize(n+2);
this->n = n+1;
}
void update(int i, int val) {
++i;
for (; i < n; i += i & -i) tree[i] += val;
}
int sum(int r) {
int res = 0;
++r;
for (; r > 0; r -= r & -r) res += tree[r];
return res;
}
int query(int l, int r) {
return sum(r) - sum(l-1);
}
};
int N;
int mx = 0;
BIT prizes;
int ans = -1;
void solve(vector<int> &indices, int l, int r, vector<int> res_l, vector<int> res_r);
vector<vector<int>> asked;
vector<int> qry(int i) {
if (i == -1) return {0, mx};
if (i == N) return {mx, 0};
if (asked[i][0] != -1) return asked[i];
vector<int> res = ask(i);
asked[i] = res;
return res;
}
int find_best(int n) {
N = n;
prizes.init(n);
asked.resize(n+1, vector<int>(2, -1));
for (int i = 0; i < min(n, 500); i++) {
vector<int> res = qry(i);
if (res[0]+res[1] == 0) return i;
mx = max(mx, res[0]+res[1]);
}
vector<int> v;
for (int i = 0; i < n; i++) v.push_back(i);
solve(v, -1, N, {0, mx}, {mx, 0});
return ans;
}
void solve(vector<int> &indices, int l, int r, vector<int> res_l, vector<int> res_r) {
if (ans != -1) return;
if (indices.empty()) return;
vector<int> v;
int i = 0, j = indices.size()-1;
while (i <= j) {
v.push_back(indices[i]);
if (i < j) v.push_back(indices[j]);
i++, j--;
}
while (!v.empty()) {
int cur = v.back();
v.pop_back();
vector<int> res = qry(cur);
if (res[0]+res[1] == 0) {
ans = cur;
return;
}
if (res[0]+res[1] != mx) {
if (!prizes.query(cur, cur)) prizes.update(cur, 1);
}
else {
int found = prizes.query(l+1, cur);
if (res[0] != res_l[0]+found) {
vector<int> search;
for (auto x : v) {
if (x < cur) search.push_back(x);
}
if (!search.empty()) {
sort(search.begin(), search.end());
solve(search, l, cur, res_l, res);
}
}
found = prizes.query(cur+1, r);
if (res[1] != res_r[1]+found) {
vector<int> search;
for (auto x : v) {
if (x > cur) search.push_back(x);
}
if (!search.empty()) {
sort(search.begin(), search.end());
solve(search, cur, r, res, res_r);
}
}
break;
}
}
}
