#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
struct fenwick_tree{
int fen[N];
bool account[N];
void update(int i){
i++;
account[i] = true;
for (; i < N; i += i & -i){
fen[i]++;
}
}
int query(int i){
i++;
int ans = 0;
for (; i > 0; i -= i & -i){
ans += fen[i];
}
return ans;
}
int query(int l, int r){
l++; r++;
return query(r) - query(l - 1);
}
} fen;
int n;
vector <int> query_answer[N];
int cnt_left[N], cnt_right[N];
int type[N];
void query(int x){
if (not query_answer[x].empty()){
return;
}
query_answer[x] = ask(x);
cnt_left[x] = query_answer[x].front();
cnt_right[x] = query_answer[x].back();
type[x] = accumulate(query_answer[x].begin(), query_answer[x].end(), 0);
}
int find_min_lollipop(){
int lo = 1, hi = n - 1;
while (lo < hi){
int mid = (lo + hi) >> 1;
int sum = 0, t = mid;
while (t){
sum += t;
t = sqrt(t - 1);
}
if (sum >= n){
hi = mid;
}
else{
lo = mid + 1;
}
}
return lo;
}
int type_lollipop;
int jump_right[N];
int search_important(int l, int r){
if (l > r){
exit(0);
}
if (l == r){
query(l);
fen.update(l);
return l;
}
int mid = (l + r) >> 1;
query(mid);
if (type[mid] == type_lollipop){
if (fen.query(mid + 1, n - 1) != cnt_right[mid]){
return search_important(mid + 1, r);
}
else{
return search_important(l, mid - 1);
}
return -1;
}
if (not fen.account[mid]){
fen.update(mid);
return mid;
}
int &idx = jump_right[mid];
while (idx < n){
query(idx);
if (type[idx] == type_lollipop){
break;
}
if (not fen.account[idx]){
fen.update(idx);
return idx;
}
idx++;
}
if (idx < n and fen.query(idx + 1, n - 1) != cnt_right[idx]){
return search_important(idx + 1, r);
}
else{
return search_important(l, mid - 1);
}
return -1;
}
int find_best(int _n){
n = _n;
int min_lollipop = find_min_lollipop();
int max_important = n - min_lollipop;
int lim = min(n, max_important + 1);
for (int i = 0; i < lim; i++){
query(i);
if (type[i] == 0){
return i;
}
}
type_lollipop = *max_element(type, type + lim);
for (int i = 0; i < lim; i++){
if (type[i] != type_lollipop){
fen.update(i);
}
}
iota(jump_right, jump_right + n, 1);
while (true){
int idx = search_important(lim, n - 1);
if (type[idx] == 0){
return idx;
}
}
return -1;
}
