#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
#define pii pair <int,int>
#define mp make_pair
#define f first
#define s second
#define pb push_back
#define en '\n'
#define all(v) v.begin(),v.end()
const int N = 2e5 + 10;
int k,mx,kol;
vector <int> was[N];
bool u[N],gd[N];
vector <pii> q;
int t[N * 4],t1[N * 4];
void build(int v,int tl,int tr) {
if(tl == tr) {
t[v] = 1;
t1[v] = 0;
return;
}
int tm = (tl + tr) / 2;
build(v + v,tl,tm);
build(v + v + 1,tm + 1,tr);
t[v] = t[v + v] + t[v + v + 1];
}
int get(int v,int tl,int tr,int x) {
if(tl == tr)return tl;
int tm = (tl + tr) / 2;
if(t[v + v] >= x)return get(v + v,tl,tm,x);
else return get(v + v + 1,tm + 1,tr,x - t[v + v]);
}
void upd(int v,int tl,int tr,int pos) {
if(tl == tr) {
t[v] = 0;
t1[v] = 1;
return;
}
int tm = (tl + tr) / 2;
if(pos <= tm)upd(v + v,tl,tm,pos);
else upd(v + v + 1,tm + 1,tr,pos);
t[v] = t[v + v] + t[v + v + 1];
t1[v] = t1[v + v] + t1[v + v + 1];
}
int get1(int v,int tl,int tr,int l,int r) {
if(tl > r || tr < l)return 0;
if(tl >= l && tr <= r)return t1[v];
int tm = (tl + tr) / 2;
return get1(v + v,tl,tm,l,r) + get1(v + v + 1,tm + 1,tr,l,r);
}
/*
8
3 2 3 1 3 3 2 3
*/
vector <int> Ask(int x) {
if(u[x])return was[x];
u[x] = 1;
kol++;
assert(kol <= 10000);
was[x] = ask(x);
return was[x];
}
int find_best(int pp) {
k = pp;
int m = (k - 1) / 2;
int mx = 1;
build(1,0,k - 1);
int pos = 0;
while(1) {
int l = 0,r = k - 1 - pos;
while(l <= r) {
int mid = (l + r) / 2;
int zap = get(1,0,k - 1,mid + 1);
vector <int> res = Ask(zap);
int sum = res[0] + res[1];
if(sum == 0)return zap;
if(sum < mx) {
pos++;
upd(1,0,k - 1,zap);
gd[zap] = 1;
break;
}
if(sum > mx) {
bool ch = 0;
for(int i = 0;i < k;i++) {
if(!gd[i] && u[i] && i != zap) {
pos++;
upd(1,0,k - 1,i);
ch = 1;
gd[i] = 1;
}
}
mx = sum;
if(ch)break;
}
res[0] -= get1(1,0,k - 1,0,zap - 1);
if(res[0] != 0) {
r = mid - 1;
}else {
l = mid + 1;
}
}
}
}
