#include <iostream>
#include <stdio.h>
#include <vector>
//#include "grader.cpp"
using namespace std;
const int mxn = 4e5 + 10,mxi = 1e9 + 10;
struct we
{
int bef,ne;
};
vector <int> pa[mxn] = {};
struct we li[mxn] = {};
//,rmq[30][mxn] = {},cou = 1
int se[mxn] = {},pil[mxn] = {},ru,mse[mxn] = {},fva[mxn] = {},nn,ma = -1,mno = -1,fr[mxn] = {},to[mxn] = {},rr;
int fima(int l,int r)
{
if(l > r)
return l;
return r;
}
int cre(int cl,int cr,int no)
{
if(cl == cr)
{
se[no] = 1;
return 0;
}
int mid = (cl+cr) / 2;
cre(cl,mid,no*2);
cre(mid+1,cr,no*2+1);
se[no] = se[no*2] + se[no*2+1];
return 0;
}
int del(int cl,int cr,int no,int tl,int tr)
{
if(cr < tl || cl > tr)
{
return 0;
}
if(cl >= tl && cr <= tr)
{
se[no] = 0;
return 0;
}
int mid = (cl+cr) / 2;
// if(se[no*2] != 0)
// {
del(cl,mid,no*2,tl,tr);
// }
// if(se[no*2])
del(mid+1,cr,no*2+1,tl,tr);
se[no] = se[no*2] + se[no*2+1];
return 0;
}
int fifr(int cl,int cr,int no,int cva)
{
int mid = (cl+cr) / 2;
if(cl == cr)
{
return cl;
}
if(se[no*2] >= cva)
{
return fifr(cl,mid,no*2,cva);
}
else
{
return fifr(mid+1,cr,no*2+1,cva - se[no*2]);
}
}
int crema(int cl,int cr,int no)
{
if(cl == cr)
{
mse[no] = fva[cl];
return 0;
}
int mid = (cl+cr) / 2;
crema(cl,mid,no*2);
crema(mid+1,cr,no*2+1);
mse[no] = fima(mse[no*2],mse[no*2+1]);
return 0;
}
int sfima(int cl,int cr,int no,int tl,int tr)
{
if(cr < tl || cl > tr)
{
return -1;
}
if(cl >= tl && cr <= tr)
{
return mse[no];
}
int mid = (cl+cr) / 2,cval,cvar;
cval = sfima(cl,mid,no*2,tl,tr);
cvar = sfima(mid+1,cr,no*2+1,tl,tr);
return fima(cval,cvar);
}
int re(int cn,int acva)
{
int i,fn,cva = 0;
if(cn < nn)
{
if(acva > ma)
{
ma = acva;
mno = cn;
}
return 0;
}
if(sfima(0,nn-2,1,fr[cn],to[cn]-1) < rr)
{
cva = 1;
}
for(i=0; i<pa[cn].size(); i++)
{
fn = pa[cn][i];
re(fn,acva + cva);
}
return 0;
}
int GetBestPosition(int n, int nc, int r, int *k, int *st, int *en)
{
nn = n;
rr = r;
int i,j,cf,ct,cn,cst = 0,cct;
for(i=0; i<n; i++)
{
pil[i] = i;
if(i < n-1)
fva[i] = *(k+i);
if(i == 0)
{
li[i] = {-1,i+1};
}
else if(i == n-1)
{
li[i] = {i-1,-1};
}
else
{
li[i] = {i-1,i+1};
}
fr[i] = i;
}
ru = n;
cre(0,n-1,1);
for(i=0; i<nc; i++)
{
cf = fifr(0,n-1,1,*(st+i) + 1);
ct = fifr(0,n-1,1,*(en+i) + 1);
fr[ru] = fr[cf];
to[ru] = ct;
fr[ct] = fr[cf];
cct = ct;
del(0,n-1,1,cf,ct-1);
cf = pil[cf];
ct = pil[ct];
pil[cct] = ru;
cn = cf;
while(cn != ct)
{
pa[ru].push_back(cn);
cn = li[cn].ne;
}
pa[ru].push_back(cn);
if(cf == cst)
{
cst = ru;
li[ru].bef = -1;
}
else
{
li[ru].bef = li[cf].bef;
li[li[cf].bef].ne = ru;
}
if(li[ct].ne == -1)
{
// cst = ru;
li[ru].ne = -1;
}
else
{
li[ru].ne = li[ct].ne;
li[li[ct].ne].bef = ru;
}
ru ++;
}
// while(1)
// {
//
// }
crema(0,n-2,1);
re(ru-1,0);
return mno;
}
//
//int main()
//{
// cout << "Hello world!" << endl;
// return 0;
//}
