#include <bits/stdc++.h>
using namespace std;
const int MX = 1e5 + 5, SMX = 1<<18;
int N, C, R;
int K[MX], S[MX], E[MX], A[MX];
struct {
int st[SMX];
void init(int i, int s, int e) {
if (s==e) { st[i]=1; return ; }
int m=(s+e)/2;
init(i*2, s, m);
init(i*2+1, m+1, e);
st[i]=st[i*2]+st[i*2+1];
}
int find(int i, int s, int e, int t) {
if (st[i]<t) return e+1;
if (s==e) return s;
int m=(s+e)/2;
if (st[i*2]>=t) return find(i*2, s, m, t);
else return find(i*2+1, m+1, e, t-st[i*2]);
}
void upd(int i, int s, int e, int l, int r) {
if (e<l||r<s||!st[i]) return ;
if (l<=s&&e<=r) { st[i]=0; return ; }
int m=(s+e)/2;
upd(i*2, s, m, l, r);
upd(i*2+1, m+1, e, l, r);
st[i]=st[i*2]+st[i*2+1];
}
}S1;
struct {
int st[SMX];
void init(int i, int s, int e) {
if (s==e) { st[i]=K[s]; return ; }
int m=(s+e)/2;
init(i*2, s, m);
init(i*2+1, m+1, e);
st[i]=max(st[i*2], st[i*2+1]);
}
int get(int i, int s, int e, int l, int r) {
if (e<l||r<s) return 0;
if (l<=s&&e<=r) return st[i];
int m=(s+e)/2;
return max(get(i*2, s, m, l, r), get(i*2+1, m+1, e, l, r));
}
}S2;
int sol() {
S1.init(1, 1, N);
S2.init(1, 1, N-1);
for (int i=1; i<=C; i++) {
int l=S1.find(1, 1, N, S[i]), r=S1.find(1, 1, N, E[i]+1)-1;
S1.upd(1, 1, N, l+1, r);
if (S2.get(1, 1, N-1, l, r-1)<R) A[l]++, A[r+1]--;
}
int mx=0, r=1;
for (int i=1; i<=N; i++) {
A[i]+=A[i-1];
if (A[i]>mx) mx=A[i], r=i;
}
return r-1;
}
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
::N=N, ::C=C, ::R=R+1;
for (int i=1; i<=N-1; i++) ::K[i]=K[i-1]+1;
for (int i=1; i<=C; i++) ::S[i]=S[i]+1, ::E[i]=E[i]+1;
return sol();
}
