// In the name of Allah
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef complex<ld> cld;
#define all(x) (x).begin(),(x).end()
#define len(x) ((ll) (x).size())
#define F first
#define S second
#define pb push_back
#define sep ' '
#define endl '\n'
#define Mp make_pair
#define kill(x) cout << x << '\n', exit(0)
#define set_dec(x) cout << fixed << setprecision(x);
#define file_io(x,y) freopen(x, "r", stdin); freopen(y, "w", stdout);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int n, q, x;
const int maxn = (1 << 17) + 4;
int a[maxn], ok[maxn]; pii Q[maxn];
int t[2 * maxn]; set<pii> st;
int tx[maxn]; set<int> stx;
vector<int> A1[maxn], A2[maxn];
void build(int v, int tl, int tr) {
if (tr - tl == 1) {
t[v] = 1;
return ;
}
int mid = (tl + tr) / 2;
build(2 * v + 1, tl, mid); build(2 * v + 2, mid, tr);
t[v] = t[2 * v + 1] + t[2 * v + 2];
}
void set_val(int v, int tl, int tr, int i, int x) {
if (i >= tr || i < tl) return ;
if (tr - tl == 1) {
t[v] = x;
return ;
}
int mid = (tl + tr) / 2;
set_val(2 * v + 1, tl, mid, i, x); set_val(2 * v + 2, mid, tr, i, x);
t[v] = t[2 * v + 1] + t[2 * v + 2];
}
int get_ind(int v, int tl, int tr, int x) {
if (tr - tl == 1) {
if (t[v] == 1) return tl;
else return tr;
}
int mid = (tl + tr) / 2;
if (t[2 * v + 1] >= x) return get_ind(2 * v + 1, tl, mid, x);
else return get_ind(2 * v + 2, mid, tr, x - t[2 * v + 1]);
}
void addx(int i, int x) {
for (++i; i < maxn; i += (i & -i)) tx[i] += x;
}
int getx(int i) {
int res = 0;
for (++i; i > 0; i -= (i & -i)) res += tx[i];
return res;
}
int GetBestPosition(int Nx, int Cx, int Rx, int Kx[], int Sx[], int Ex[]) {
n = Nx; q = Cx; x = Rx;
for (int i = 0; i < n - 1; i++) a[i] = (Kx[i] > x);
for (int i = 0; i < q; i++) Q[i] = Mp(Sx[i], Ex[i]);
build(0, 0, n);
for (int i = 0; i < n; i++) st.insert(Mp(i, 1));
for (int i = 0; i < q; i++) {
int l = Q[i].F, r = Q[i].S;
l = get_ind(0, 0, n, l + 1); r = get_ind(0, 0, n, r + 2) - 1;
int x = 0; Q[i] = Mp(l, r);
while (true) {
auto it = st.lower_bound(Mp(l, -1));
if (it == st.end() || (*it).F > r) break;
pii f = *it; x += f.S;
st.erase(f); set_val(0, 0, n, f.F, 0);
}
st.insert(Mp(l, x)); set_val(0, 0, n, l, 1);
}
for (int i = 0; i < n - 1; i++) {
if (a[i] == 1) stx.insert(i);
}
for (int i = 0; i < q; i++) {
int l = Q[i].F, r = Q[i].S;
A1[l].pb(i); A2[r].pb(i);
auto it = stx.lower_bound(l);
if (it != stx.end() && (*it) < r) ok[i] = 0;
else ok[i] = 1;
}
pii res = Mp(-1, -1); stx.clear();
for (int i = 0; i < n; i++) {
for (int j : A1[i]) {
if (!ok[j]) stx.insert(j);
else addx(j, 1);
}
int ind = q - 1;
if (!stx.empty()) ind = (*stx.begin()) - 1;
int x = getx(ind);
if (x > res.F) res = Mp(x, i);
for (int j : A2[i]) {
if (!ok[j]) stx.erase(j);
else addx(j, -1);
}
}
return res.S;
}
