#include <bits/stdc++.h>
#define LOG 20
#define MAX 100010
using namespace std;
typedef pair<int,int> pii;
class SegmentTree
{
public:
int getLeft(int i) { return 2*i; }
int getRight(int i) { return 2*i + 1; }
void build(int node, int l, int r)
{
lazy[node] = -1;
if(l == r) return void( sum[node] = 1 );
int m = (l + r)/2;
build(getLeft(node) , l , m);
build(getRight(node) , m + 1 , r);
sum[node] = sum[ getLeft(node) ] + sum[ getRight(node) ];
}
void refresh(int node, int l, int r)
{
if(lazy[node] == -1) return;
int lz = lazy[node];
lazy[node] = -1;
sum[node] = lz*(r - l + 1);
if(l == r) return;
lazy[ getLeft(node) ] = lz;
lazy[ getRight(node) ] = lz;
}
void update(int node, int l, int r, int i, int j, int v)
{
refresh(node , l , r);
if(j < l || r < i) return;
if(i <= l && r <= j)
{
lazy[node] = v;
refresh(node , l , r);
return;
}
int m = (l + r)/2;
update(getLeft(node) , l , m , i , j , v);
update(getRight(node) , m + 1 , r , i , j , v);
sum[node] = sum[ getLeft(node) ] + sum[ getRight(node) ];
}
int bs(int node, int l, int r, int k)
{
refresh(node , l , r);
if(l == r) return l;
int m = (l + r)/2;
int sumLeft = sum[ getLeft(node) ];
if(sumLeft >= k) return bs(getLeft(node) , l , m , k);
return bs(getRight(node) , m + 1 , r , k - sumLeft);
}
private:
int sum[4*MAX];
int lazy[4*MAX];
};
int n, c, r;
int v[MAX];
int L[MAX];
int R[MAX];
int dp[LOG][MAX];
int nearestLeft[MAX];
int nearestRight[MAX];
pii interval[2*MAX];
set<pii> activedIntervals;
set<pii>::iterator it;
SegmentTree SEG;
void buildTree()
{
SEG.build(1 , 1 , n);
for(int g = 1 ; g <= n ; g++)
{
interval[g] = {g , g};
activedIntervals.insert({g , g});
}
int curInterval = n;
for(int g = 1 ; g <= c ; g++)
{
int newL = SEG.bs(1 , 1 , n , L[g]);
int newR = SEG.bs(1 , 1 , n , R[g]);
interval[ ++curInterval ] = {newL , newR};
it = activedIntervals.lower_bound({newL , 0});
vector<pii> aux;
for( ; it->first <= newR && it != activedIntervals.end() ; it++)
{
dp[0][ it->second ] = curInterval;
aux.push_back( *it );
}
while( !aux.empty() )
{
activedIntervals.erase( aux.back() );
aux.pop_back();
}
activedIntervals.insert({newL , curInterval});
SEG.update(1 , 1 , n , newL , newR , 0);
SEG.update(1 , 1 , n , newL , newL , 1);
}
dp[0][ curInterval ] = 0;
for(int k = 1 ; k < LOG ; k++)
{
for(int g = 1 ; g <= curInterval ; g++)
{
int jump = dp[k - 1][g];
dp[k][g] = dp[k - 1][jump];
}
}
}
int distLCA(int i, int j)
{
int dist = 0;
for(int k = LOG - 1 ; k >= 0 ; k--)
{
int jump = dp[k][j];
if(jump == 0) continue;
if(interval[jump].first > i || i > interval[jump].second)
{
j = jump;
dist += (1 << k);
}
}
return dist;
}
int GetBestPosition(int N, int C, int ranking, int *K, int *S, int *E)
{
n = N; c = C; r = ranking;
for(int g = 1 ; g <= C ; g++)
{
L[g] = S[g - 1] + 1;
R[g] = E[g - 1] + 1;
}
for(int g = 1 ; g <= N ; g++)
v[g] = K[g - 1];
buildTree();
nearestLeft[1] = -1;
nearestRight[n] = -1;
for(int g = 2 ; g <= n ; g++)
{
if(v[g - 1] > ranking) nearestLeft[g] = g - 1;
else nearestLeft[g] = nearestLeft[g - 1];
}
for(int g = n - 1 ; g >= 1 ; g--)
{
if(v[g] > ranking) nearestRight[g] = g + 1;
else nearestRight[g] = nearestRight[g + 1];
}
int qtdCombats = -1;
int bestPosition;
for(int g = 1 ; g <= n ; g++)
{
int ansLeft = distLCA(nearestLeft[g] , g);
int ansRight = distLCA(nearestRight[g] , g);
int ans = min(ansLeft , ansRight);
if(ans > qtdCombats)
{
qtdCombats = ans;
bestPosition = g;
}
}
return bestPosition - 1;
}
/*int main()
{
int nn, cc, rr;
scanf("%d %d %d",&nn,&cc,&rr);
int kk[nn], ss[cc + 1], ee[cc + 1];
for(int g = 0 ; g < nn - 1 ; g++)
scanf("%d",&kk[g]);
for(int g = 0 ; g < cc ; g++)
scanf("%d %d",&ss[g],&ee[g]);
printf("%d\n",GetBestPosition(nn , cc , rr , kk , ss , ee));
}*/
