#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
struct BIT {
int n;
vector<int> tree;
void init(int n) {
tree.resize(n+1);
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 mx = 0;
BIT prizes;
int ans = -1;
void solve(int l, int r, int tot);
vector<vector<int>> asked;
vector<int> qry(int i) {
if (asked[i][0] != -1) return asked[i];
vector<int> res = ask(i);
asked[i] = res;
return res;
}
int find_best(int n) {
prizes.init(n);
asked.resize(n+1, vector<int>(2, -1));
for (int i = 0; i < min(n, 3); i++) {
vector<int> res = qry(i);
if (res[0]+res[1] == 0) return i;
mx = max(mx, res[0]+res[1]);
}
solve(0, n-1, mx);
return ans;
}
void solve(int l, int r, int tot) {
if (ans != -1) return;
int mid = (l+r)/2;
vector<int> res = qry(mid);
vector<int> res2 = qry(r);
vector<int> res3 = qry(l);
if (res[0]+res[1] == 0) {
ans = mid;
return;
}
if (res2[0]+res2[1] == 0) {
ans = r;
return;
}
if (res3[0]+res3[1] == 0) {
ans = l;
return;
}
if (res[0]+res[1] != mx) {
if (!prizes.query(mid, mid)) prizes.update(mid, 1);
res[0]++;
}
if (res[0] != res2[0]) {
int cnt = res2[0]-res[0];
int found = prizes.query(mid, r);
if (found < cnt) solve(mid, r, cnt);
}
if (res[0] != res3[0]) {
int cnt = res[0]-res3[0];
int found = prizes.query(l, mid);
if (found < cnt) solve(l, mid, cnt);
}
}
