#include <bits/stdc++.h>
#include "prize.h"
#ifdef ONPC
#include "t_debug.cpp"
#else
#define debug(...) 42
#endif
#define sz(a) ((int)(a).size())
using namespace std;
using ll = long long;
const int INF = 1e9;
const ll INFL = 1e18;
const int RANDOM = chrono::high_resolution_clock::now().time_since_epoch().count();
mt19937 rng(RANDOM);
template<typename T, typename U> istream& operator>>(istream& is, pair<T, U>& p) { return is >> p.first >> p.second; }
const int N = 2e5, LOGN = 17, MOD = 1e9+7;
struct Fenwick {
int n;
vector<ll> tree;
Fenwick(int n) : n(n) {
tree.assign(n, 0);
}
void inc(int pos) {
if (sum(pos, pos) == 1) return;
for (; pos < n; pos |= (pos + 1)) {
tree[pos]++;
}
}
ll sum(int r) { // [0, r]
ll ans = 0;
for (; r >= 0; r = (r & (r + 1)) - 1) {
ans += tree[r];
}
return ans;
}
ll sum(int l, int r) { // [l, r]
return sum(r) - sum(l - 1);
}
};
int find_best(int n) {
vector<int> res;
int mx = 0, L = 0, R = n-1;
for (int i = 0; i < min(n, 500); i++) {
res = ask(i);
if (res[0] + res[1] > mx) {
mx = res[0] + res[1];
L = i;
}
}
for (; R >= L; R--) {
res = ask(R);
if (res[0] + res[1] == mx) break;
}
int ans = -1;
function<void(int,int,int)> solve = [&](int L, int R, int count)->void {
if (!count) return;
if (L > R) return;
if (R - L + 1 == count) {
if (~ans) return;
for (int i = L; i <= R; i++) {
auto res = ask(i);
if (res[0] + res[1] == 0) ans = i;
break;
}
return;
}
vector<int> res;
while (true) {
res = ask(L);
if (res[0] + res[1] == 0) {
ans = L;
return;
}else if (res[0] + res[1] == mx) break;
else L++;
}
int mid1 = (L + R) / 2;
int mid2 = mid1;
while (true) {
auto res2 = ask(mid2);
if (res2[0] + res2[1] < mx) {
if (res2[0] + res2[1] == 0) {
ans = mid2;
return;
}
mid2++;
} else {
solve(L+1, mid1-1, res[1] - res[0]);
solve(mid2+1, R, count - (res[1] - res[0]));
}
}
};
solve(L, R, res[0]);
return ans;
}
/*
█████ █████ ███ ████
▒▒███ ▒▒███ ▒▒▒ ▒▒███
███████ ████████ ███████ ████ ▒███ █████ ████ ██████ ████████
███▒▒███ ▒▒███▒▒███ ███▒▒███ ▒▒███ ▒███ ▒▒███ ▒███ ███▒▒███▒▒███▒▒███
▒███ ▒███ ▒███ ▒▒▒ ▒███ ▒███ ▒███ ▒███ ▒███ ▒███ ▒███ ▒███ ▒███ ▒▒▒
▒███ ▒███ ▒███ ▒███ ▒███ ▒███ ▒███ ▒███ ▒███ ▒███ ▒███ ▒███
▒▒████████ █████ ▒▒████████ █████ █████ ▒▒███████ ▒▒██████ █████
▒▒▒▒▒▒▒▒ ▒▒▒▒▒ ▒▒▒▒▒▒▒▒ ▒▒▒▒▒ ▒▒▒▒▒ ▒▒▒▒▒███ ▒▒▒▒▒▒ ▒▒▒▒▒
███ ▒███
▒▒██████
▒▒▒▒▒▒
*/
