#include<bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
template<typename T> bool chkmax(T &x,T y){return x<y?x=y,1:0;}
template<typename T> bool chkmin(T &x,T y){return x>y?x=y,1:0;}
int n,a[100005],fnw[100005],sl[100005],sr[100005],fa[100005],dep[100005],pos=1;
vector<int> g[100005];
int getf(int x){return fa[x]==x?x:fa[x]=getf(fa[x]);}
void modify(int x,int v){
for(;x<100005;x+=x&-x)fnw[x]+=v;
}
int query(int x){
int s=0;
for(;x>0;x-=x&-x)s+=fnw[x];
return s;
}
int getp(int x){
int l=0,r=100004,p=0;
while(l<=r){
int m=(l+r)/2;
if(query(m)<x)p=m,l=m+1; else r=m-1;
}
return p+1;
}
void dfs(int x){
if(x<=n)return (void)(pos=x);
sort(g[x].begin(),g[x].end(),[&](int i,int j){return dep[i]>dep[j]||(dep[i]==dep[j]&&sl[i]<sl[j]);});
dfs(g[x][0]);
}
int GetBestPosition(int N,int C,int R,int*K,int*S,int*E){
a[1]=R;n=N;
for(int i=2;i<=N;i++)a[i]=K[i-2];
for(int i=1;i<=N;i++)a[i]=(a[i]>R?1:0);
set<int> st;
for(int i=1;i<=N;i++)modify(i,1),st.insert(i);
for(int i=1;i<=N;i++)sl[i]=sr[i]=fa[i]=i;
for(int i=N+1;i<=N+C;i++)fa[i]=i,sl[i]=N+C,sr[i]=0;
for(int i=1;i<=C;i++){
int l=getp(S[i-1]+1),r=getp(E[i-1]+1);
assert(l>=1&&r<=n);
while(1){
auto it=st.lower_bound(l);
if(it==st.end()||*it>r)break;
chkmax(dep[N+i],dep[getf(*it)]);
chkmin(sl[N+i],sl[getf(*it)]);
chkmax(sr[N+i],sr[getf(*it)]);
g[N+i].pb(getf(*it));
modify(*it,-1);
st.erase(it);
}
modify(l,1);
st.insert(l);
fa[getf(l)]=N+i;
dep[N+i]++;
// for(int j=1;j<=N;j++)printf("%d ",query(j)-query(j-1));puts("");
}
int ans=0;
for(int i=1;i<=N;i++)a[i]=a[i-1]+a[i];
for(int i=N+1;i<=N+C;i++)if(a[sr[i]]==a[sl[i]]&&ans<dep[i])ans=dep[i];
for(int i=N+1;i<=N+C;i++)if(a[sr[i]]==a[sl[i]]&&ans==dep[i]){dfs(i);break;}
return pos-1;
}
