#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
#define ff first
#define ss second
const int SIZE = 1 << 17;
struct ST {
pii A[2 * SIZE];
int l[2 * SIZE];
void push(int nn, int v) {
A[nn].ff += v;
l[nn] += v;
}
void ldown(int nn, int ns, int ne) {
push(nn << 1, l[nn]);
push(nn << 1 | 1, l[nn]);
l[nn] = 0;
}
void init(int nn, int s, int e) {
if (s == e) {
A[nn].ss = -s;
return;
}
int m = s + e >> 1;
init(nn << 1, s, m);
init(nn << 1 | 1, m + 1, e);
A[nn] = max(A[nn << 1], A[nn << 1 | 1]);
}
void update(int nn, int ns, int ne, int s, int e, int v) {
if (ns > e || ne < s) return;
if (s <= ns && ne <= e) {
push(nn, v);
return;
}
int m = ns + ne >> 1;
ldown(nn, ns, ne);
update(nn << 1, ns, m, s, e, v);
update(nn << 1 | 1, m + 1, ne, s, e, v);
A[nn] = max(A[nn << 1], A[nn << 1 | 1]);
}
int query() {
return -A[1].ss;
}
} seg;
int L[100001], R[100001], par[100001];
int fnd(int x) { return par[x] == x ? x : par[x] = fnd(par[x]); }
void uni(int x, int y) {
x = fnd(x), y = fnd(y);
if (x == y) return;
par[y] = x;
L[x] = min(L[x], L[y]);
R[x] = max(R[x], R[y]);
}
int GetBestPosition(int N, int C, int R_, int *K, int *S, int *E) {
for (int i = 0; i < N; ++i) {
L[i] = R[i] = i;
par[i] = i;
}
seg.init(1, 0, N);
for (int i = 0; i < C; ++i) {
int s = 0, a;
for (int j = 0; j < S[i]; ++j) s = R[fnd(s)] + 1;
a = s;
for (int j = S[i]; j < E[i]; ++j) {
int t = R[fnd(s)] + 1;
uni(s, t);
s = t;
}
a = fnd(a);
int t = 0;
for (int j = L[a]; j < R[a]; ++j) t = max(t, K[j]);
if (t < R_) seg.update(1, 0, N, L[a], R[a], 1);
}
return seg.query();
}
