#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;
for(int i=1;i<=n-1;i++) a[i] = K[i-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] - 1;
s = 1, e = n;
while(s <= e){
mid = (s+e)/2;
if(query(&top,1,n,1,mid).F > x){
e = mid-1;
}
else s = 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){
e = mid-1;
}
else s = mid+1;
}
r = s;
update(&top,1,n,l,r-1);
//printf("!! %d %d\n",l,r);
int val_r = a[r], val_l = query(&top,1,n,l,r-1).S;
if(val_r < v && val_l < v){
arr[l]++, arr[r+1]--;
}
else if(val_r > v && val_l < v && r - l > 1){
arr[l]++, arr[r]--;
}
}
int sum = 0, ans=0;
for(int i=1;i<=n+1;i++){
sum += arr[i];
ans = max(ans, sum);
}
return ans;
}
