#include <bits/stdc++.h> using namespace std; const int N = 2e5+5; int up[N][25]; int t[N*4]; vector <int> lazy(4*N,-1); int k[N]; int p[N]; void applay(int node, int val, int l, int r) { t[node] = val*(r-l+1); lazy[node] = val; } void push(int node, int l, int r){ if (lazy[node] != -1) { int mid = (l+r)/2; applay(node*2,lazy[node],l,mid); applay(node*2+1,lazy[node],mid+1,r); lazy[node] = -1; } } void update(int node, int l, int r, int L, int R, int val) { if (l > R ||r < L) return; if (l >= L && r <= R) { applay(node,val,l,r); return; } push(node, l, r); int mid = (l+r)/2; update(node*2,l,mid,L,R,val); update(node*2+1,mid+1,r,L,R,val); t[node] = t[node*2]+t[node*2+1]; } int get(int node, int l, int r, int val) { if (l == r) { return l; } int mid = (l+r)/2; if (t[node*2] >= val) { return get(node*2,l,mid,val); } return get(node*2+1,mid+1,r,val-t[node*2]); } int merge(int x, int y) { if (k[x] > k[y]) return x; return y; } int getmax(int l, int r) { int lg = log2(r-l+1); return merge(up[l][lg],up[r-(1<<lg)+1][lg]); } int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) { N--; for (int i = 0; i < N; i++) { k[i] = K[i]; up[i][0] = i; } for (int i = 1; i <= 20; i++) { for (int j = 0; j < N; j++) { if (j + (1 << i) > N) break; up[j][i] = merge(up[j][i-1],up[j+(1<<(i-1))][i-1]); } } for (int i = 0; i < N; i++) { update(1,1,N,i,i,1); } 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); int mx = -1; if (l <= r) mx = k[getmax(l-1,r-1)]; update(1,1,N,l+1,r,0); if (mx < R) { p[l]++; p[r+1]--; } } int ans = 0; for (int i = 1; i <= N; i++) { p[i] = p[i-1] + p[i]; if (p[ans] < p[i]) ans = i; } return ans; }