#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 (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 c, int r_val, int *K, int *S, int *E) { vector<int> pref(n + 1, 0); for (int i = 0; i < n - 1; i++) { pref[i + 1] = pref[i] + (K[i] > r_val); } build(1, 1, n); vector<int> jump(n + 1); for (int i = 1; i <= n; i++) jump[i] = i + 1; vector<int> d(n + 2, 0); for (int i = 0; i < c; i++) { int l = get(1, 1, n, S[i] + 1); int r = get(1, 1, n, E[i] + 1); for (int j = jump[l]; j <= r;) { update(1, 1, n, j); int nxt = jump[j]; jump[j] = jump[r]; j = nxt; } jump[l] = jump[r]; if (pref[r - 1] - pref[l - 1] == 0) { d[l]++; d[r + 1]--; } } 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; }