#include <iostream>
#include <stdio.h>
#include <fstream>
#include <string.h>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <list>
#include <set>
#include <deque>
#include <utility>
#include <sstream>
#include <queue>
#include <stack>
#include <bitset>
#include <math.h>
#include <algorithm>
#include <limits.h>
using namespace std ;
const int No = 2e5;
long long mx[10*No] ;
vector <long long> l, r ;
vector <pair<long long, long long>> in;
vector <long long> vals;
void update (int node, int lw, int rg, int a, long long v) {
if ( lw == a && rg == a ) {
mx[node] = v ;
return ;
}
int m = (lw + rg) >> 1 ;
if ( a <= m ) update ( node << 1, lw, m, a, v) ;
else update ( (node<<1) + 1, m+1, rg, a, v ) ;
mx[node] = max ( mx[node<<1], mx[(node<<1)+1] ) ;
}
long long query ( int node, int lw, int rg, int a, int b ) {
if ( b < lw || rg < a ) return 0 ;
if ( a <= lw && rg <= b ) return mx[node] ;
int m = (lw + rg) >> 1 ;
return max ( query(node<<1, lw, m, a, b), query ((node<<1)+1, m+1, rg, a, b) );
}
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
for ( int i = 0 ; i < N-1 ; ++i ) vals.push_back(K[i]) ;
for ( int i = 0 ; i < N-1 ; ++i ) in.push_back ({0, -i}), l.push_back (i), r.push_back (i), update (1, 0, No-1, i, K[i]) ;
pair <long long, long long> ans = {INT_MIN, -1};
for ( int i = 0 ; i < C ; ++i ) {
pair <long long, long long> incur = {INT_MIN, -1};
long long lcur = INT_MAX, rcur = INT_MIN, mxcur = INT_MIN;
for ( int j = S[i] ; j <= E[i] ; ++j ) {
if ( S[i] >= vals.size() ) break ;
incur = max ( incur, in[S[i]] ) ;
lcur = min ( lcur, l[S[i]] ) ;
rcur = max ( rcur, r[S[i]] ) ;
mxcur = max ( mxcur, vals[S[i]] ) ;
vals.erase ( vals.begin() + S[i] ) ;
l.erase ( l.begin() + S[i] ) ;
r.erase ( r.begin() + S[i] ) ;
in.erase ( in.begin() + S[i] ) ;
}
vals.insert (vals.begin() + S[i], mxcur ) ;
l.insert ( l.begin() + S[i], lcur ) ;
r.insert ( r.begin() + S[i], rcur ) ;
in.insert ( in.begin() + S[i], incur ) ;
if ( S[i] < in.size() ) in[S[i]].first++ ;
if ( S[i] < in.size() && query (1, 0,No-1, l[S[i]], r[S[i]]-1) < R ) ans = max ( ans, in[S[i]] ) ;
}
return -ans.second ;
}
