#include <bits/stdc++.h>
#include "prize.h"
using namespace std;
const int N = 200000 + 7;
int n;
int t_pre[4 * N];
int t_suf[4 * N];
vector<int> ret[N];
void upd_pre(int v, int tl, int tr, int i, int cnt) {
if (i < tl) {
return;
}
if (tr <= i) {
t_pre[v] = min(t_pre[v], cnt);
} else {
int tm = (tl + tr) / 2;
upd_pre(2 * v, tl, tm, i, cnt);
upd_pre(2 * v + 1, tm + 1, tr, i, cnt);
}
}
void upd_suf(int v, int tl, int tr, int i, int cnt) {
if (tr < i) {
return;
}
if (i <= tl) {
t_suf[v] = min(t_suf[v], cnt);
} else {
int tm = (tl + tr) / 2;
upd_suf(2 * v, tl, tm, i, cnt);
upd_suf(2 * v + 1, tm + 1, tr, i, cnt);
}
}
int get_pre(int v, int tl, int tr, int i) {
if (tr < tl) {
return N;
}
int sol = t_pre[v];
if (tl < tr) {
int tm = (tl + tr) / 2;
sol = min(sol, get_pre(2 * v, tl, tm - 1, i));
sol = min(sol, get_pre(2 * v + 1, tm + 1, tr, i));
}
return sol;
}
int get_suf(int v, int tl, int tr, int i) {
if (tr < tl) {
return N;
}
int sol = t_suf[v];
if (tl < tr) {
int tm = (tl + tr) / 2;
sol = min(sol, get_suf(2 * v, tl, tm - 1, i));
sol = min(sol, get_suf(2 * v + 1, tm + 1, tr, i));
}
return sol;
}
void upd_pre(int i, int cnt) {
upd_pre(1, 0, n - 1, i, cnt);
}
void upd_suf(int i, int cnt) {
upd_suf(1, 0, n - 1, i, cnt);
}
int cnt_pre(int i) {
return min(i - 1, get_pre(1, 0, n - 1, i));
}
int cnt_suf(int i) {
return min(n - 1 - i, get_suf(1, 0, n - 1, i));
}
void upd(int i) {
if (ret[i].empty()) {
ret[i] = ask(i);
upd_pre(i, ret[i][0]);
upd_suf(i, ret[i][1]);
}
}
int rep(int l, int r, int q) {
assert(q >= 0);
if (l > r || q == 0) {
return 0;
}
int m = (l + r) / 2;
q--;
upd(m);
int x = cnt_pre(m);
int y = cnt_suf(m);
if (x == 0 && y == 0) {
return m;
}
if (x == 0) {
return rep(m + 1, r, q);
} else {
return rep(l, m - 1, q);
}
/// c0 / c1 = x / y
/// c0 / (c0 + c1) = x / (x + y)
/// c0 / q = x / (x + y)
/// c0 = x * q / (x + y)
int c0 = (long long) x * q / (x + y);
int c1 = q - c0;
int val = rep(l, m - 1, c0);
if (val) {
return val;
} else {
return rep(m + 1, r, c1);
}
}
int find_best(int nn) {
n = nn;
for (int i = 0; i < 4 * N; i++) {
t_pre[i] = t_suf[i] = N;
}
return rep(0, n - 1, 9999 - 100);
}
