#include<bits/stdc++.h>
using namespace std;
#include<bits/extc++.h>
using namespace __gnu_pbds;
template<typename T>
using order_statistics_tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define ff first
#define ss second
#define all(x) (x).begin(), (x).end()
#define pb push_back
typedef int64_t lld;
typedef pair<int, int> pii;
typedef long double ld;
template<typename T1, typename T2>
ostream& operator<<(ostream& out, pair<T1, T2> p){
return out << "(" << p.ff << ", " << p.ss << ")";
}
template<typename Iter>
ostream& outIt(ostream& out, Iter b, Iter e){
for(Iter i = b; i != e; i++)
out << (i==b?"":" ") << *i;
return out;
}
template<typename T>
ostream& operator<<(ostream& out, vector<T> v){
return outIt(out << '[', all(v)) << ']';
}
vector<pii> rounds;
vector<int> lcnt, oops;
/*
struct node{
node*L = 0, *R = 0;
int l, r;
int val = 0;
node(int ll, int rr){
l = ll, r = rr;
if(l == r)val = l;
else L = new node(l, l+r>>1), R = new node((l+r>>1)+1, r);
}
void down(){ L->val += val, R->val += val, val = 0; }
void update(int ll, int rr, int x){
if(ll <= l && rr >= r)val += x;
else if(ll > r || rr < l || ll > rr)return;
else L->update(ll, rr, x), R->update(ll, rr, x);
}
int query(int i){
if(l == r && l == i)return val;
else return down(), (i <= (l+r>>1)?L:R)->query(i);
}
} *roots, *roote;
*/
order_statistics_tree<pii> reps;
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
/*
roots = new node(0, N-1), roote = new node(1, N);
for(int i = 0; i < C; i++){
rounds.pb({roots->query(S[i]), roote->query(E[i])});
roots->update(S[i]+1, N, E[i]-S[i]);
roote->update(S[i], N, E[i]-S[i]);
}
*/
for(int i = 0; i < N; i++)reps.insert({i, i});
for(int i = 0; i < C; i++){
auto b = reps.find_by_order(S[i]), e = reps.find_by_order(E[i]), ne = next(e);
rounds.pb({b->ff, e->ss});
for(auto i = b; i != ne; i=reps.erase(i));
reps.insert(rounds.back());
}
lcnt.resize(N);
for(int i = N-2; i >= 0; i--)
lcnt[i] = K[i] < R ? 1+lcnt[i+1] : 0;
oops.resize(N+1);
for(auto& p: rounds)
if(lcnt[p.ff] >= p.ss-p.ff)oops[p.ff]++, oops[p.ss+1]--;
for(int i = 1; i <= N; i++)oops[i] += oops[i-1];
//cout << rounds << endl << lcnt << endl << oops << endl;
return max_element(all(oops))-oops.begin();
//return 0;
}
