#include <bits/stdc++.h>
using namespace std;
struct fen{
int n;
vector<int> ftt;
fen(int N){
n=N;
ftt.resize(n+1, 0);
}
void up(int i, int v){
for (;i<=n;i+=i&-i)ftt[i]+=v;
}
int sum(int i){
int res=0;
for (int p=i;p;p-=p&-p)res+=ftt[p];
return res;
}
int bs(int v){
int res=n, id=0, sum=0;
for (int i=20; i>=0; --i)if (id+(1<<i)<=n){
if (sum+ftt[id+(1<<i)]>=v)res=id+(1<<i);
else id+=(1<<i), sum+=sum+ftt[id];
}
return res;
}
}*ft;
int GetBestPosition(int n, int q, int k, int *K, int *L, int *R){
vector<int> vect(n+1), psum(n+1, 0), p(n+1, 1), d(n+1, 0);
ft = new fen(n);
for (int i=1; i<n; ++i)vect[i]=K[i-1];
for (int i=1; i<=n; ++i){
if (i!=1)psum[i]=psum[i-1]+(vect[i-1]>k);
ft->up(i, 1);
p[i]=i+1;
}
for (int i=0; i<q; ++i){
int l=ft->bs(L[i]+1), r=ft->bs(R[i]+1);
for (int j=l+1; j<=r; j=p[j])ft->up(j, -1);
p[l]=r+1;
if (psum[l]==psum[r])++d[l], --d[r+1];
}
int mx=0, best=0;
for (int i=1, sum=0; i<=n; ++i){
sum+=d[i];
if (sum>mx)mx=sum, best=i-1;
}
return best;
}
