#include <bits/stdc++.h>
//#include "bits_stdc++.h"
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define endl '\n'
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define input(x) scanf("%lld", &x);
#define input2(x, y) scanf("%lld%lld", &x, &y);
#define input3(x, y, z) scanf("%lld%lld%lld", &x, &y, &z);
#define input4(x, y, z, a) scanf("%lld%lld%lld%lld", &x, &y, &z, &a);
#define print(x, y) printf("%lld%c", x, y);
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x,y) cerr << #x << " is " << x << " " << #y << " is " << y << endl;
#define show3(x,y,z) cerr << #x << " is " << x << " " << #y << " is " << y << " " << #z << " is " << z << endl;
#define all(x) x.begin(), x.end()
#define discretize(x) sort(x.begin(), x.end()); x.erase(unique(x.begin(), x.end()), x.end());
#define FOR(i, x, n) for (ll i =x; i<=n; ++i)
#define RFOR(i, x, n) for (ll i =x; i>=n; --i)
using namespace std;
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
using namespace __gnu_pbds;
#define ordered_set tree<pi, null_type, less<pi>, rb_tree_tag, tree_order_statistics_node_update>
//#define ordered_multiset tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update>
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ld, ll> pd;
typedef pair<string, ll> psl;
typedef pair<ll, ll> pi;
typedef pair<pi, ll> pii;
typedef pair<pi, pi> piii;
ll const INF = 1e13;
struct node{
int s, e, m;
pi val;
ll lazy;
node *l, *r;
node (int S, int E)
{
s = S, e = E, m = (s+e)/2;
val = mp(0, -s);
lazy = 0;
l=r=nullptr;
}
void create()
{
if(s != e && l==nullptr)
{
l = new node(s, m);
r = new node(m+1, e);
}
}
void propogate()
{
if (lazy==0) return;
create();
val.f+=lazy;
if (s != e){
l->lazy+=lazy;
r->lazy+=lazy;
}
lazy=0;
}
void update(int S, int E, ll V)
{
propogate();
if(s==S && e==E) lazy += V;
else{
create();
if(E <= m) l->update(S, E, V);
else if (m < S) r->update(S, E, V);
else l->update(S, m, V),r->update(m+1, E, V);
l->propogate(),r->propogate();
val = max(l->val, r->val);
}
}
pi query(int S, int E)
{
propogate();
if(s == S && e == E) return val;
create();
if(E <= m) return l->query(S, E);
else if(S >= m+1) return r->query(S, E);
else return max(l->query(S, m), r->query(m+1, E));
}
} *root1, *root2;
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E)
{
ll n = N;
ordered_set dis;
for (ll i=0; i<n; ++i) dis.insert(mp(i, i));
vector<pi> realq;
for (ll i=0; i<C; ++i)
{
ll l = LLONG_MAX, r = LLONG_MIN;
for (ll j=S[i]; j<=E[i]; ++j)
{
auto now = dis.find_by_order(S[i]);
l = min(l, now->f);
r = max(r, now->s);
dis.erase(now);
}
realq.pb(mp(l, r));
dis.insert(mp(l, r));
}
pi ans = mp(0, 0);
root1 = new node(0, n-2);
root2 = new node(0, n-1);
for (ll i=0; i<n-1; ++i) root1->update(i, i, K[i]);
for (pi u: realq)
{
pi maxx = root1->query(u.f, u.s-1);
if (maxx.f > R) root2->update(u.f, u.s, -INF);
else root2->update(u.f, u.s, 1);
ans = max(ans, root2->query(0, n-1));
}
return ans.s*-1LL;
}
