#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
using namespace std;
const int maxn = 100100;
pair<int,int> intervals[maxn];
int lc[maxn], rc[maxn], n, r, q;
int bit[maxn], curr_intv[maxn], parent[maxn];
int pref[maxn], answ[maxn];
void update(int index, int val) {
for(int i=index;i<=n;i+=i&(-i)) {
bit[i] += val;
}
}
int query(int x) {
int sum = 0;
for(int i=x;i>0;i-=i&(-i)) {
sum += bit[i];
}
return sum;
}
void preprocess() {
for(int i=0;i<=n;i++) {
lc[i] = i - 1;
rc[i] = i + 1;
}
rc[n] = -1;
}
int bin_search(int val) {
int index = n;
if(query(index) < val) return n+1;
for(int cekor = n; cekor > 0; cekor/=2) {
while(index - cekor >= 0 && query(index-cekor)>=val) index-=cekor;
}
return index;
}
int recursion(int i) {
if(answ[i] != -1) return answ[i];
int l = intervals[i].first;
int r = intervals[i].second;
int after = r - 1;
int before = l - 1;
int cnt = pref[after] - pref[before];
if(cnt == 0) {
answ[i] = 1;
if(parent[i] != -1) answ[i] += recursion(parent[i]);
}
else {
answ[i] = 0;
}
return answ[i];
}
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
n = N; r = R; q = C;
preprocess();
for(int i=1;i<=n;i++) update(i, 1);
memset(curr_intv, -1, sizeof(curr_intv));
memset(parent, -1, sizeof(parent));
memset(answ, -1, sizeof(answ));
for(int i=0;i<q;i++) {
int l = bin_search(S[i]+1);
int r = bin_search(E[i]+2) - 1;
intervals[i] = mp(l, r);
if(curr_intv[l] != -1) {
parent[curr_intv[l]] = i;
curr_intv[l] = i;
}
else curr_intv[l] = i;
//cout<<"Q:"<<i<<" -> "<<l<<" "<<r<<"\n";
for(int j=rc[l];j<=r && j!=-1;j=rc[j]) {
//cout<<"upd: "<<j<<"\n";
// set this value to 0
if(curr_intv[j] != -1) {
parent[curr_intv[j]] = i;
curr_intv[j] = i;
}
else curr_intv[j] = i;
rc[lc[j]] = rc[j];
lc[rc[j]] = lc[j];
update(j, -1);
}
}
for(int i=1;i<n;i++) {
pref[i] = pref[i-1];
if(K[i-1] > r) pref[i]++;
}
int maxm = 0, ind = 1;
for(int i=0;i<q;i++) {
int curr = recursion(i);
if(curr > maxm) {
maxm = curr;
ind = intervals[i].first;
}
else if(curr == maxm) {
ind = min(ind, intervals[i].first);
}
}
return ind - 1;
}
/*int arr[maxn], s[maxn], e[maxn];
int main() {
//ifstream fin("input.txt");
int n, c, r;
cin>>n>>c>>r;
for(int i=0;i<n-1;i++) cin>>arr[i];
for(int i=0;i<c;i++) cin>>s[i]>>e[i];
cout<<GetBestPosition(n, c, r, arr, s, e);
return 0;
}*/
