#include<bits/stdc++.h>
using namespace std;
#define FOR(i, x, y) for(int i = x; i < y; ++i)
#define pb push_back
int G;
vector<int> base;
int TRACK;
void update(int ind, int x, vector<int>& fen){
ind++;
while (ind < fen.size()){
fen[ind] += x;
ind += ind&(-ind);
}
}
int query(int ind, vector<int> &fen){
int ans = 0;
ind++;
while(ind > 0){
ans += fen[ind];
ind -= ind &(-ind);
}
return ans;
}
struct node{
vector<int> e;
vector<int> w;
int c = 1;
int par = -1;
int ind = -1;
int parind= -1;
int l = -1;
int r = -1;
int score = 0;
};
vector<node> g;
int Find(int cur, int ind){
// cout << ind << "\n" << flush;
if (ind < 0){
cin >> cur;
}
// cout << "cur, ind " << cur << ", " << ind << "\n";
if (ind == 0 && g[cur].e.size() == 0){
return cur;
}
int l = -1;
int r = g[cur].w.size() - 2;
while (r > l + 1){
int mid = (l + r)/2;
if (query(mid, g[cur].w) > ind){
r = mid;
}
else{
l = mid;
}
}
// FOR(i, 0, g[cur].w.size()){
// cout << query(i, g[cur].w) << " ";
// }
// cout << "\n";
// cout << "l r " << l << " " << r << endl;
int tmp = query(l, g[cur].w);
if (tmp <= ind){
ind -= tmp;
}
// cout << g[cur].e[r] << " " << ind << endl;
return Find(g[cur].e[r], ind);
/*FOR(i, 0, g[cur].e.size()){
int nex = g[cur].e[i];
int wex = g[nex].c;
if (wex > ind){
return Find(nex, ind);
}
else if (wex <= ind){
ind -= wex;
}
}*/
return cur;
}
void Add(int cur, int amount){
// cout << "here with "<< cur << " size " << amount << "\n";
g[cur].w.resize(amount + 1);
FOR(i, 0, amount){
g[cur].e.pb(G);
g[G].par = cur;
g[G].parind = i;
update(i, 1, g[cur].w);
G++;
}
g[cur].c += amount - 1;
int par = g[cur].par;
while(par != -1){
update(g[cur].parind, amount - 1, g[par].w);
g[par].c += amount - 1;
cur = par;
par = g[cur].par;
}
}
void initbase(int cur){
if (g[cur].e.size() == 0){
base[TRACK] = cur;
g[cur].ind = TRACK;
g[cur].l = TRACK;
g[cur].r = TRACK + 1;
TRACK++;
return;
}
int L = INT_MAX;
int R = -1;
FOR(i, 0, g[cur].e.size()){
int nex = g[cur].e[i];
initbase(nex);
L = min(L, g[nex].l);
R = max(R, g[nex].r);
}
g[cur].l = L;
g[cur].r = R;
}
vector<int> seg;
void update(int ind, int x){
ind += seg.size()/2;
seg[ind] = x;
ind /= 2;
while (ind > 0){
seg[ind] = max(seg[2*ind], seg[2*ind + 1]);
ind /= 2;
}
}
int R;
int query(int l, int r){
//inclusive-exclusive
l += seg.size()/2;
r += seg.size()/2;
int ans = 0;
while (r > l){
if (l % 2 == 1){
ans = max(ans, seg[l]);
l++;
}
if (r % 2 == 1){
ans = max(ans, seg[r - 1]);
}
l /= 2;
r /= 2;
}
return ans;
}
void process(int cur){
int high = query(g[cur].l, g[cur].r - 1);
if (high < R){
g[cur].score = g[g[cur].par].score + 1;
}
else{
g[cur].score = 0;
}
}
int GetBestPosition(int N, int C, int r, int *K, int *S, int *E) {
R = r;
g.resize(2*N);
base.resize(N);
TRACK = 0;
G = 1;
seg.resize(2*(N-1));
FOR(i, 0, N - 1){
update(i,K[i]);
}
for(int i = C - 1; i >= 0; --i){
int ind = Find(0,S[i]);
Add(ind, E[i] - S[i] + 1);
}
initbase(0);
FOR(i, 0, G){
process(i);
}
/* cout << "Done\n";
cout << G << "\n";
FOR(i, 0, G){
cout << i << ":\n";
cout << "e: ";
FOR(j, 0, g[i].e.size()){
cout << g[i].e[j] << " ";
}
cout << "\n";
cout << "c = " << g[i].c << "\n";
cout << "par = " << g[i].par << "\n";
cout << "(l, r) = (" << g[i].l << ", " << g[i].r << ")\n";
cout << "score = " << g[i].score << "\n";
cout << "------------------------------\n";
}
FOR(i, 0, base.size()){
cout << base[i] << " ";
}
cout << "\n";
FOR(i, 0, seg.size()){
cout << i << ": " << seg[i] << "\n";
}*/
int smax = 0;
int ind = 0;
FOR(i, 0, base.size()){
if (g[base[i]].score > smax){
smax = g[base[i]].score;
ind = i;
}
}
return ind;
}
