#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+5;
int fen[MAXN],sp[MAXN][20];
vector< pair<int,int> > vq[MAXN];
set<int> st;
int getlog(long long n) { return 63-__builtin_clzll(n); }
void update(int i,int n,int val) { for(;i<=n;i+=i&-i) fen[i]+=val; }
int get(int i) { int ans=0;for(;i;i-=i&-i) ans+=fen[i];return ans; }
int walk(int n,int val) { int ans=0;for(int i=getlog(n);i+1;i--) if(ans+(1<<i)<=n&&val>=fen[ans+(1<<i)]) val-=fen[ans+=(1<<i)];return ans+1; }
int rmq(int l,int r)
{
int lg=getlog(r-l+1);
return max(sp[l][lg],sp[r-(1<<lg)+1][lg]);
}
int GetBestPosition(int N,int C,int r,int *K,int *S,int *E)
{
vector<int> L,R;
for(int i=1;i<N;i++)
{
update(i,N,1);
sp[i][0]=K[i-1];
}
update(N,N,1);
for(int j=1;(1<<j)<N;j++) for(int i=1;i<=N-(1<<j);i++) sp[i][j]=max(sp[i][j-1],sp[i+(1<<(j-1))][j-1]);
for(int i=0;i<C;i++)
{
int lt=walk(N,S[i]),rt=walk(N,E[i]+1)-1;
L.push_back(lt),R.push_back(rt),lt=walk(N,S[i]+1);
while(lt<=rt) update(lt,N,-1),lt=walk(N,S[i]+1);
}
int ans=0,pos=0;
for(int i=1;i<=N;i++)
{
int sum=0;
for(int j=0;j<C;j++) if(L[j]<=i&&i<=R[j])
{
if(rmq(L[j],R[j]-1)<r) sum++;
else break;
}
if(ans<sum) ans=sum,pos=i-1;
}
return pos;
}
