#include <bits/stdc++.h>
using namespace std;
#define debug(args...) kout("[ " + string(#args) + " ]", args)
void kout() { cerr << endl; }
template <class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ',kout(b...); }
template <class T> void pary(T L, T R) { while (L != R) cerr << *L << " \n"[++L==R]; }
const int MAXN = 100000;
const int L = 20;
class Bit {
private:
int arr[MAXN+1];
int N;
inline int lb(int a) {
return a &- a;
}
public:
void build(int n) {
N = n;
for (int i = 1; i <= N; i++)
for (int j = i; j <= N; j+=lb(j))
arr[j]++;
}
void mdy(int a) {
a++;
for (int i = a; i <= N; i+=lb(i))
arr[i]--;
}
int qry(int a) {
a++;
int sum = 0;
for (int i = a; i; i-=lb(i))
sum += arr[i];
return sum;
}
int fndL(int a) {
a++;
int now = 0, s = 0;
for (int i = __lg(N); i >= 0; i--)
if (now + (1<<i) <= N && s + arr[now + (1<<i)] < a)
now += (1<<i), s += arr[now];
return now;
}
int fndR(int a) {
a++;
int now = 0, s = 0;
for (int i = __lg(N); i >= 0; i--) {
if (now + (1<<i) <= N && s + arr[now + (1<<i)] <= a)
now += (1<<i), s += arr[now];
}
return now-1;
}
} bit;
class SparseTable {
private:
int arr[MAXN+1][L];
int N;
public:
void build(int n, int *K) {
N = n;
for (int i = 0; i < N; i++)
arr[i][0] = K[i];
for (int i = 1; i < L; i++)
for (int j = 0; j < N-(1<<i)+1; j++)
arr[j][i] = max(arr[j][i-1], arr[j+(1<<(i-1))][i-1]);
}
int qry(int L, int R) {
int k = __lg(R-L+1);
return max(arr[L][k], arr[R-(1<<k)+1][k]);
}
} st;
class Seg {
private:
int arr[MAXN*4+5];
bool flag[MAXN*4+5];
int tag[MAXN*4+5];
void pull(int now) {
arr[now] = max(arr[now*2] * flag[now*2], arr[now*2+1] * flag[now*2+1]);
flag[now] = (flag[now*2] || flag[now*2+1]);
}
void push(int now, int len) {
arr[now] += tag[now];
if (len > 1) {
tag[now*2 ] += tag[now];
tag[now*2+1] += tag[now];
if (!flag[now]) {
flag[now*2 ] = false;
flag[now*2+1] = false;
}
}
tag[now] = 0;
}
public:
void build(int now, int l, int r) {
arr[now] = 0;
flag[now] = true;
if (l == r) return;
int mid = l + r >> 1;
build(now*2 , l, mid);
build(now*2+1,mid+1,r);
pull(now);
return;
}
void add(int ml, int mr, int now, int l, int r) {
push(now, r-l+1);
if (ml <= l && r <= mr) {
tag[now]++;
push(now, r-l+1);
return;
} else if (l > mr || r < ml) return;
int mid = l + r >> 1;
add(ml, mr, now*2 , l, mid);
add(ml, mr, now*2+1,mid+1,r);
pull(now);
return;
}
void stp(int ml, int mr, int now, int l, int r) {
push(now, r-l+1);
if (ml <= l && r <= mr) {
flag[now] = false;
push(now, r-l+1);
return;
}
int mid = l + r >> 1;
stp(ml, mr, now*2 , l, mid);
stp(ml, mr, now*2+1,mid+1,r);
pull(now);
return;
}
int qry() {
return arr[1] * flag[1];
}
} seg;
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
bit.build(N);
for (int i = 0; i < C; i++) {
int L = bit.fndL(S[i]);
int R = bit.fndR(E[i]);
for (int j = L+1; j <= R; j++)
if (bit.qry(j) > bit.qry(j-1))
bit.mdy(j);
S[i] = L, E[i] = R;
}
st.build(N-1, K);
seg.build(1, 0, N-1);
int ans = 0;
for (int i = 0; i < C; i++) {
if (st.qry(S[i], E[i]-1) < R) {
continue;
seg.add(S[i], E[i], 1, 0, N-1);
} else {
continue;
seg.stp(S[i], E[i], 1, 0, N-1);
}
ans = max(ans, seg.qry());
}
return ans;
}
