#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define sz(x) (int)x.size()
int n,c,r;
int po[100005],fen[100005];
vector<pair<int,int> > v;
struct node
{
int mx = 0;
node *l = NULL, *r = NULL;
} *root;
void f_up(int idx,int val)
{
idx++;
while(idx < 100005)
{
fen[idx] += val;
idx += idx & -idx;
}
}
int f_que(int idx)
{
int ret = 0;
idx++;
while(idx > 0)
{
ret += fen[idx];
idx -= idx & -idx;
}
return ret;
}
node* build(int l,int r)
{
node *ptr = new node;
if(l == r)
{
ptr->mx = po[l];
return ptr;
}
int mid = (l + r) / 2;
ptr->l = build(l,mid);
ptr->r = build(mid + 1, r);
ptr->mx = max(ptr->l->mx, ptr->r->mx);
return ptr;
}
int ll,rr;
int query(node *ptr,int l,int r)
{
if(ll <= l && r <= rr) return ptr->mx;
if(r < ll || rr < l) return 0;
int mid = (l + r) / 2;
return max(query(ptr->l, l, mid), query(ptr->r, mid + 1, r));
}
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E)
{
n = N, c = C, r = R;
for(int i = 0; i < n; i++)
po[i] = K[i];
root = build(0, n - 1);
for(int i = 0; i < c; i++)
{
int s = S[i], e = E[i];
s += f_que(s);
e += f_que(e);
f_up(S[i], e - s);
v.pb({s,e});
}
int ans = 0;
for(int i = 0; i < n; i++)
{
int cnt = 0;
for(int j = 0; j < c; j++)
{
int s = v[j].f;
int e = v[j].s;
if(s >= i) s--;
if(e >= i) e--;
ll = s, rr = e;
int gt = query(root, 0, n - 1);
if(s <= i && i <= e)
{
if(r > gt) cnt++;
else break;
}
}
ans = max(ans, cnt);
}
return ans;
}
