#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
int a[N];
struct SegmentTree {
int T[4 * N];
#define mid ((l + r) >> 1)
void build(int i, int l, int r) {
if (l == r) { T[i] = 1; return; }
build(i << 1, l, mid);
build(i << 1 | 1, mid + 1, r);
T[i] = T[i << 1] + T[i << 1 | 1];
}
void upd(int i, int l, int r, int p) {
if (l == r) { T[i] = 0; return; }
if (mid >= p) upd(i << 1, l, mid, p);
else upd(i << 1 | 1, mid + 1, r, p);
T[i] = T[i << 1] + T[i << 1 | 1];
}
int get(int i, int l, int r, int k) {
if (l == r) return l;
if (T[i << 1] >= k) return get(i << 1, l, mid, k);
else return get(i << 1 | 1, mid + 1, r, k - T[i << 1]);
}
#undef mid
} IT;
struct Seg {
int l, r, v;
bool operator < (const Seg& rhs) const {
return l > rhs.l;
}
};
int bit[N];
void upd(int x, int y) {
for (int i = x; i < N; i += i & -i) bit[x] = max(bit[x], y);
}
int get(int x) {
int ret = 0;
for (int i = x; i > 0; i -= i & -i) ret = max(ret, bit[i]);
return ret;
}
int GetBestPosition(int n, int C, int R, int *K, int *S, int *E) {
vector<Seg> seg;
IT.build(1, 0, n - 1);
for (int i = 0; i < C; ++i) {
vector<int> vec;
for (int j = S[i]; j <= E[i]; ++j) {
vec.push_back(IT.get(1, 0, n - 1, j + 1));
}
int l = vec[0];
a[vec[0]]++;
for (int j = 1; j < vec.size(); ++j) {
a[vec[0]] = max(a[vec[0]], a[vec[j]] + 1);
}
int r = (E[i] == (IT.T[1] - 1)) ? n : (IT.get(1, 0, n - 1, E[i] + 2) - 1);
seg.push_back({l, r, a[vec[0]]});
for (int j = 1; j < vec.size(); ++j) {
IT.upd(1, 0, n - 1, vec[j]);
}
}
vector<Seg> seg2;
for (int i = 0; i < (n - 1); ++i) {
if (K[i] > R) continue;
int r = i;
while (r < (n - 1) && K[r] <= R) r++;
seg2.push_back({i, r, 0});
}
sort(seg.begin(), seg.end());
sort(seg2.begin(), seg2.end());
int ptr = 0, res = 0;
for (auto i : seg2) {
while (ptr < seg.size() && seg[ptr].l >= i.l) {
upd(seg[ptr].r + 1, seg[ptr].v), ++ptr;
}
res = max(res, get(i.r + 1));
}
return res;
}
