#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
//#pragma GCC optimize("O3")
//#pragma GCC target("avx,avx2,fma")
//#pragma GCC optimization ("unroll-loops")
//#pragma GCC target("avx,avx2,sse,sse2,sse3,sse4,popcnt")
using namespace std;
using namespace __gnu_pbds;
#define int long long
#define float long double
#define elif else if
#define endl "\n"
#define mod 1000000007
#define pi acos(-1)
#define eps 0.000000001
#define inf 1000'000'000'000'000'000LL
#define FIXED(a) cout << fixed << setprecision(a)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define time_init auto start = std::chrono::high_resolution_clock::now()
#define time_report \
auto end = std::chrono::high_resolution_clock::now(); \
std::cout << std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count() << " ms" << endl
#define debug(x) \
{ cerr << #x << " = " << x << endl; }
#define len(x) (int) x.size()
#define sqr(x) ((x) * (x))
#define cube(x) ((x) * (x) * (x))
#define bit(x, i) (((x) >> (i)) & 1)
#define set_bit(x, i) ((x) | (1LL << (i)))
#define clear_bit(x, i) ((x) & (~(1LL << (i))))
#define toggle_bit(x, i) ((x) ^ (1LL << (i)))
#define low_bit(x) ((x) & (-(x)))
#define count_bit(x) __builtin_popcountll(x)
#define srt(x) sort(all(x))
#define rsrt(x) sort(rall(x))
#define mp make_pair
#define maxel(x) (*max_element(all(x)))
#define minel(x) (*min_element(all(x)))
#define maxelpos(x) (max_element(all(x)) - x.begin())
#define minelpos(x) (min_element(all(x)) - x.begin())
#define sum(x) (accumulate(all(x), 0LL))
#define product(x) (accumulate(all(x), 1LL, multiplies<int>()))
#define gcd __gcd
#define lcm(a, b) ((a) / gcd(a, b) * (b))
#define rev(x) (reverse(all(x)))
#define shift_left(x, k) (rotate(x.begin(), x.begin() + k, x.end()))
#define shift_right(x, k) (rotate(x.rbegin(), x.rbegin() + k, x.rend()))
#define is_sorted(x) (is_sorted_until(all(x)) == x.end())
#define is_even(x) (((x) &1) == 0)
#define is_odd(x) (((x) &1) == 1)
#define pow2(x) (1LL << (x))
struct custom_hash {
static uint64_t splitmix64(uint64_t x) {
// http://xorshift.di.unimi.it/splitmix64.c
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
template<typename T>
using min_heap = priority_queue<T, vector<T>, greater<T>>;
template<typename T>
using max_heap = priority_queue<T, vector<T>, less<T>>;
template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T>
using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T>
using matrix = vector<vector<T>>;
template<typename T>
using graph = vector<vector<T>>;
using hashmap = gp_hash_table<int, int, custom_hash>;
template<typename T>
vector<T> vect(int n, T val) {
return vector<T>(n, val);
}
template<typename T>
vector<vector<T>> vect(int n, int m, T val) {
return vector<vector<T>>(n, vector<T>(m, val));
}
template<typename T>
vector<vector<vector<T>>> vect(int n, int m, int k, T val) {
return vector<vector<vector<T>>>(n, vector<vector<T>>(m, vector<T>(k, val)));
}
template<typename T>
vector<vector<vector<vector<T>>>> vect(int n, int m, int k, int l, T val) {
return vector<vector<vector<vector<T>>>>(n, vector<vector<vector<T>>>(m, vector<vector<T>>(k, vector<T>(l, val))));
}
template<typename T>
matrix<T> new_matrix(int n, int m, T val) {
return matrix<T>(n, vector<T>(m, val));
}
template<typename T>
graph<T> new_graph(int n) {
return graph<T>(n);
}
template<class T, class S>
inline bool chmax(T &a, const S &b) {
return (a < b ? a = b, 1 : 0);
}
template<class T, class S>
inline bool chmin(T &a, const S &b) {
return (a > b ? a = b, 1 : 0);
}
using i8 = int8_t;
using i16 = int16_t;
using i32 = int32_t;
using i64 = int64_t;
using i128 = __int128_t;
using u8 = uint8_t;
using u16 = uint16_t;
using u32 = uint32_t;
using u64 = uint64_t;
using u128 = __uint128_t;
template<typename T>
using vec = vector<T>;
using pII = pair<int, int>;
template<typename T>
using enumerated = pair<T, int>;
template<int maxSz>
struct SegmentTree {
private:
array<int, maxSz << 2> stree;
array<int, maxSz << 2> pushes;
int sz;
public:
int combine(int a, int b) {
return a + b;
}
void build(int v, int tl, int tr, const vec<int> &a) {
if (tl == tr) {
stree[v] = a[tl];
pushes[v] = -1;
return;
}
build(v << 1, tl, (tl + tr) >> 1, a);
build(v << 1 | 1, ((tl + tr) >> 1) + 1, tr, a);
stree[v] = combine(stree[v << 1], stree[v << 1 | 1]);
pushes[v] = -1;
}
void push(int v, int tl, int tr) {
if (pushes[v] == -1) return;
if (tl == tr)
return;
int tm = (tl + tr) >> 1;
stree[v << 1] = pushes[v] * (tm - tl + 1);
stree[v << 1 | 1] = pushes[v] * (tr - tm);
pushes[v << 1] = pushes[v];
pushes[v << 1 | 1] = pushes[v];
pushes[v] = -1;
}
void init(const vec<int> &v) {
int n = len(v);
sz = n;
build(1, 0, n - 1, v);
}
void update_(int v, int tl, int tr, int l, int r, int val) {
if (l == tl and r == tr) {
stree[v] = val * (r - l + 1);
pushes[v] = val;
push(v, tl, tr);
return;
}
push(v, tl, tr);
int tm = (tl + tr) >> 1;
if (r <= tm) {
update_(v * 2, tl, tm, l, r, val);
} elif (l > tm) {
update_(v * 2 + 1, tm + 1, tr, l, r, val);
} else {
update_(v * 2, tl, tm, l, tm, val);
update_(v * 2 + 1, tm + 1, tr, tm + 1, r, val);
}
stree[v] = combine(stree[v * 2], stree[v * 2 + 1]);
}
void update(int l, int r, int val) {
update_(1, 0, sz - 1, l, r, val);
}
pair<int, int> left_most_(int v, int tl, int tr, int l, int r, int x) {
if (l > r) return {-1, 0};
push(v, tl, tr);
if (l == tl and r == tr and stree[v] < x) return {-1, stree[v]};
if (tl == tr) return {tl, 0};
int tm = (tl + tr) >> 1;
auto [res, sm] = left_most_(v * 2, tl, tm, l, min(r, tm), x);
if (res != -1) return {res, sm};
auto [res2, sm2] = left_most_(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r, x - sm);
if (res2 != -1) return {res2, sm2};
sm += sm2;
return {-1, sm};
}
int get_(int v, int tl, int tr, int l, int r) {
push(v, tl, tr);
if (l == tl and r == tr) {
return stree[v];
}
int tm = (tl + tr) >> 1;
if (r <= tm) {
return get_(v * 2, tl, tm, l, r);
} elif (l > tm) {
return get_(v * 2 + 1, tm + 1, tr, l, r);
}
return combine(get_(v * 2, tl, tm, l, tm), get_(v * 2 + 1, tm + 1, tr, tm + 1, r));
}
int left_most(int x) {
int tl = 0;
int tr = sz - 1;
while (tl < tr) {
int tm = (tl + tr) >> 1;
if (get_(1, 0, sz - 1, 0, tm) < x) {
tl = tm + 1;
} else {
tr = tm;
}
}
if (get_(1, 0, sz - 1, 0, tl) < x) return -1;
return tl;
}
};
struct PrefixSum {
int n;
vector<int> pref;
explicit PrefixSum(const vector<int> &a) {
n = len(a);
pref = vect(n, 0LL);
pref[0] = a[0];
for (int i = 1; i < n; i++) {
pref[i] = pref[i - 1] + a[i];
}
}
int get(int l, int r) {
if (l == 0) {
return pref[r];
} else {
return pref[r] - pref[l - 1];
}
}
};
template<typename T>
struct range_fenvik {
private:
vector<T> diff_tree;
vector<T> diff_mul_tree;
void _add(int id, T val) {
for (int i = id; i < len(diff_tree); i += low_bit(i)) {
diff_tree[i] += val;
diff_mul_tree[i] += val * id;
}
}
void _add_range(int l, int r, T val) {
_add(l, val);
if (r + 1 < len(diff_tree))
_add(r + 1, -val);
}
T _get(int id) {
T res = 0;
for (int i = id; i > 0; i -= low_bit(i))
res += diff_tree[i] * (id + 1) - diff_mul_tree[i];
return res;
}
public:
range_fenvik() = default;
explicit range_fenvik(int n) {
diff_tree.resize(n + 1, 0);
diff_mul_tree.resize(n + 1, 0);
}
explicit range_fenvik(const vector<T> &a) {
diff_tree.resize(len(a) + 1, 0);
diff_mul_tree.resize(len(a) + 1, 0);
for (int i = 0; i < len(a); ++i) {
add(i, a[i]);
}
}
void add(int id, T val) {
_add_range(id + 1, id + 1, val);
}
void add_range(int l, int r, T val) {
_add_range(l + 1, r + 1, val);
}
T get_pref(int id) {
return _get(id + 1);
}
T get(int x) {
return get(x, x);
}
T get(int l, int r) {
if (l == 0)
return _get(r + 1);
return _get(r + 1) - _get(l);
}
};
SegmentTree<200000> st1;
int solve(int n, int c, int R, const vec<int> &k, vec<pair<int, int>> segs) {
vec<int> t(n, 2);
st1.init(t);
auto disable = [&](int l, int r) {
// for (int i = l; i <= r; i++) {
// t[i] = 0;
// }
// t[l] = 1;
// t[r] = 1;
// return;
st1.update(l, r, 0);
st1.update(l, l, 1);
st1.update(r, r, 1);
};
auto findk = [&](int id) {
if (id == -1) return -1LL;
// for (int i = 0; i < n; i++) {
// id -= t[i];
// if (id <= 0) {
// return i;
// }
// }
// return n;
int res = st1.left_most(id);
if (res == -1) res = n;
return res;
};
for (int i = 0; i < c; i++) {
int f = findk(segs[i].first * 2 + 1);
int s = findk(segs[i].second * 2 + 2);
segs[i] = {f, s};
disable(f, s);
}
int best = 0;
int id = 0;
vec<int> v(n);
v[0] = 1;
for (int i = 0; i < n - 1; i++)
v[i + 1] = k[i] > R;
PrefixSum ps(v);
range_fenvik<int> d(n);
auto inc = [&](int l, int r, int val) {
if (l > r) return;
chmin(r, n - 1);
d.add_range(l, r, val);
};
for (auto [l, r]: segs) {
if (ps.get(l, r) > 1) continue;
if (ps.get(l, r) == 0) {
inc(l, r, 1);
}
if (ps.get(l, r) == 1 and v[l] == 1) {
inc(l, r, 1);
}
}
int best_id = 0;
for (int i = 0; i < n; i++) {
if (chmax(best, d.get(i))) {
best_id = i;
}
}
return best_id;
}
i32 GetBestPosition(i32 N, i32 C, i32 R, i32 *K, i32 *S, i32 *E) {
vec<int> k(K, K + N - 1);
vec<pair<int, int>> segs;
for (int i = 0; i < C; i++) {
segs.emplace_back(S[i], E[i]);
}
return solve(N, C, R, k, segs);
}
