#include<bits/stdc++.h>
using namespace std;
#define MAXN 100005
#define INF 1000000007
#define F first
#define S second
int n,c,v,a[MAXN],s,e,mid,x,l,r,arr[MAXN];
typedef pair<int,int> paa;
struct node{
int val,lazy,mx;
node *l, *r;
};
node top;
void build(node *pos,int be,int ed){
if(be == ed){
pos->val = 1;
pos->lazy = 0;
pos->mx = a[be];
return;
}
pos->l = new node, pos->r = new node;
int mid = (be + ed) / 2;
build(pos->l,be,mid), build(pos->r,mid+1,ed);
pos->lazy = 0;
pos->val = pos->l->val + pos->r->val;
pos->mx = max(pos->l->mx,pos->r->mx);
}
void update(node *pos,int be,int ed,int x,int y){
if(pos->lazy){
pos->lazy = 0;
pos->val = 0;
pos->mx = -INF;
if(be != ed) pos->l->lazy = 1, pos->r->lazy = 1;
}
if(be > ed || y < be || ed < x) return;
if(x <= be && ed <= y){
pos->val = 0;
pos->mx = -INF;
if(be != ed) pos->l->lazy = 1, pos->r->lazy = 1;
return;
}
int mid = (be+ed)/2;
update(pos->l,be,mid,x,y), update(pos->r,mid+1,ed,x,y);
pos->val = pos->l->val + pos->r->val;
pos->mx = max(pos->l->mx,pos->r->mx);
}
paa query(node *pos,int be,int ed,int x,int y){
if(pos->lazy){
pos->lazy = 0;
pos->val = 0;
pos->mx = -INF;
if(be != ed) pos->l->lazy = 1, pos->r->lazy = 1;
}
if(be > ed || y < be || ed < x) return {0,-INF};
if(x <= be && ed <= y) return {pos->val,pos->mx};
int mid = (be+ed)/2;
paa L = query(pos->l,be,mid,x,y), R = query(pos->r,mid+1,ed,x,y);
return {L.F+R.F,max(L.S,R.S)};
}
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
n = N,c = C, v = R+1;
for(int i=1;i<=n-1;i++) a[i] = K[i-1] + 1;
a[n] = 0;
build(&top,1,n);
for(int i=1;i<=c;i++){
S[i-1]++, E[i-1]++;
//printf("??%d %d\n",S[i-1],E[i-1]);
x = S[i-1];
s = 1, e = n;
if(x == 1){
l = 1;
}
else{
while(s <= e){
mid = (s+e)/2;
//printf("!!!!! (%d %d) %d %d \n",s,e,mid,query(&top,1,n,1,mid).F);
if(query(&top,1,n,1,mid).F < x){
s = mid+1;
}
else e = mid-1;
}
l = s;
}
x = E[i-1];
s = 1, e = n;
while(s <= e){
mid = (s+e)/2;
if(query(&top,1,n,1,mid).F <= x){
s = mid+1;
}
else e = mid-1;
}
r = e;
int val_r = a[r], val_l = query(&top,1,n,l,r-1).S;
//printf("!! %d %d : %d %d\n",l,r,val_l,val_r);
if(val_l < v){
arr[l]++, arr[r+1]--;
}
if(l < r) update(&top,1,n,l,r-1);
}
int sum = 0, ans, mxx=-INF;
for(int i=1;i<=n+1;i++){
sum += arr[i];
if(sum > mxx){
mxx = sum;
ans = i-1;
}
}
return ans;
}
/*
6 5 5
0 1 2 3 4
0 1
0 1
0 1
0 1
0 1
6 5 5
0 1 2 3 4
0 1
0 1
0 1
0 1
0 1
6 5 5
0 1 2 3 4
4 5
3 4
2 3
1 2
0 1
*/
