#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;
const int N = 1e5 + 10 , Lg = 17;
int n , ar[N] , c , R , l[N] , r[N] , rmq[N][Lg] , lg[N];
struct SEG1{
int sum[N << 2];
void Build(int node = 1 , int nl = 0 , int nr = n)
{
sum[node] = nr - nl;
if(nl + 1 == nr)
return;
int mid = (nl + nr) >> 1 , lc = node << 1 , rc = lc | 1;
Build(lc , nl , mid);
Build(rc , mid , nr);
}
void Zero(int l , int r , int node = 1 , int nl = 0 , int nr = n)
{
if(r <= nl || nr <= l)
return;
if(l <= nl && nr <= r)
{
sum[node] = 0;
return;
}
int mid = (nl + nr) >> 1 , lc = node << 1 , rc = lc | 1;
Zero(l , r , lc , nl , mid); Zero(l , r , rc , mid , nr);
sum[node] = sum[lc] + sum[rc];
}
int Get(int val , int node = 1 , int nl = 0 , int nr = n)
{
if(nl + 1 == nr)
return nl;
int mid = (nl + nr) >> 1 , lc = node << 1 , rc = lc | 1;
if(val <= sum[lc])
return Get(val , lc , nl , mid);
return Get(val - sum[lc] , rc , mid , nr);
}
} sl , sr;
struct SEG{
pair <int , int> mx[N << 2];
int lzy[N << 2];
void Build(int node = 1 , int nl = 0 , int nr = n)
{
mx[node] = make_pair(0 , -nl);
if(nl + 1 == nr)
return;
int mid = (nl + nr) >> 1 , lc = node << 1 , rc = lc | 1;
Build(lc , nl , mid);
Build(rc , mid , nr);
}
void Shift(int node , int lc , int rc)
{
if(lzy[node] == 0)
return;
mx[lc].F += lzy[node];
mx[rc].F += lzy[node];
lzy[lc] += lzy[node];
lzy[rc] += lzy[node];
lzy[node] = 0;
}
void Add(int l , int r , int node = 1 , int nl = 0 , int nr = n)
{
if(r <= nl || nr <= l)
return;
if(l <= nl && nr <= r)
{
mx[node].F++;
lzy[node]++;
return;
}
int mid = (nl + nr) >> 1 , lc = node << 1 , rc = lc | 1;
Add(l , r , lc , nl , mid);
Add(l , r , rc , mid , nr);
mx[node] = max(mx[lc] , mx[rc]);
}
} seg;
int Get_mx(int l , int r)
{
int tmp = lg[r - l];
return max(rmq[l][tmp] , rmq[r - (1 << tmp)][tmp]);
}
int GetBestPosition(int nn , int cc , int rr , int *kk , int *ss , int *ee)
{
n = nn;
for(int i = 0 ; i < n - 1 ; i++)
{
ar[i] = kk[i];
rmq[i][0] = ar[i];
}
c = cc; R = rr;
for(int i = 0 ; i < c ; i++)
{
l[i] = ss[i];
r[i] = ee[i];
}
lg[1] = 0;
for(int i = 2 ; i < N ; i++)
lg[i] = lg[i / 2] + 1;
for(int i = 1 ; i < Lg ; i++) for(int j = 0 ; j + (1 << i) < n ; j++)
rmq[j][i] = max(rmq[j][i - 1] , rmq[j + (1 << (i - 1))][i - 1]);
sl.Build();
sr.Build();
seg.Build();
for(int i = 0 ; i < c ; i++)
{
l[i] = sl.Get(l[i] + 1);
r[i] = sr.Get(r[i] + 1);
sl.Zero(l[i] + 1 , r[i] + 1);
sr.Zero(l[i] , r[i]);
int mx = Get_mx(l[i] , r[i]);
if(mx < R)
seg.Add(l[i] , r[i] + 1);
}
return abs(seg.mx[1].S);
}
