#include <bits/stdc++.h> using namespace std; const int MXN = 200005; int tree[MXN * 4]; void build(int node, int l, int r) { if (l == r) { tree[node] = 1; return; } int mid = (l + r) >> 1; build(node << 1, l, mid); build(node << 1 | 1, mid + 1, r); tree[node] = tree[node << 1] + tree[node << 1 | 1]; } void update(int node, int l, int r, int pos) { if (l == r) { tree[node] = 0; return; } int mid = (l + r) >> 1; if (pos <= mid) update(node << 1, l, mid, pos); else update(node << 1 | 1, mid + 1, r, pos); tree[node] = tree[node << 1] + tree[node << 1 | 1]; } int get(int node, int l, int r, int k) { if (tree[node] < k) return -1; if (l == r) return l; int mid = (l + r) >> 1; if (tree[node << 1] >= k) return get(node << 1, l, mid, k); return get(node << 1 | 1, mid + 1, r, k - tree[node << 1]); } int GetBestPosition(int n, int q, int m, int *K, int *L, int *R) { vector<int> pref(n + 2, 0), jump(n + 2), d(n + 2, 0); build(1, 1, n); for (int i = 1; i <= n; i++) { int K1 = (i < n) ? K[i - 1] : 2e9; pref[i + 1] = pref[i] + (K1 > m); jump[i] = i + 1; } for (int i = 0; i < q; i++) { int l = get(1, 1, n, L[i] + 1); int r = get(1, 1, n, R[i] + 2); if (r == -1) r = n + 1; for (int j = jump[l]; j < r; ) { update(1, 1, n, j); int next_j = jump[j]; jump[j] = r; j = next_j; } jump[l] = r; if (pref[l] == pref[r - 1]) { d[l]++; d[r]--; } } int mx = -1, best = 0, cur = 0; for (int i = 1; i <= n; i++) { cur += d[i]; if (cur > mx) { mx = cur; best = i - 1; } } return best; }