#include <bits/stdc++.h>
#define pb emplace_back
#define pii pair<int,int>
#define ff first
#define ss second
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;
class Seg {
private:
struct node {
int mmax, pos, c;
node() {}
node(int v, int p) {
mmax = v, pos = p, c = 0;
}
} arr[MAXN*4+5];
bool tag[MAXN*4+5];
void pull(int now) {
auto &nd = arr[now];
auto &L = arr[now*2], &R = arr[now*2+1];
if (L.mmax > R.mmax) {
nd = L, nd.c += R.c;
} else {
nd = R, nd.c += L.c;
}
}
void push(int now, int len) {
if (!tag[now]) return;
auto &nd = arr[now];
nd.mmax = nd.pos = -1;
nd.c = len;
if (len > 1) {
tag[now*2 ] = true;
tag[now*2+1] = true;
}
tag[now] = false;
}
public:
void build(int now, int l, int r, vector <int> &cur) {
if (l == r) {
arr[now] = node(cur[l], l);
return;
}
int mid = l + r >> 1;
build(now*2 , l, mid, cur);
build(now*2+1,mid+1,r, cur);
pull(now);
return;
}
void mdy(int ml, int mr, int now, int l, int r) {
push(now, r-l+1);
if (ml <= l && r <= mr) {
tag[now] = true;
push(now, r-l+1);
return;
} else if (l < mr || r < ml) return;
int mid = l + r >> 1;
mdy(ml, mr, now*2 , l, mid);
mdy(ml, mr, now*2+1,mid+1,r);
pull(now);
return;
}
pii qry(int ql, int qr, int now, int l, int r) {
push(now, r-l+1);
if (ql <= l && r <= qr) {
return pii(arr[now].mmax, arr[now].pos);
} else if (l > qr || r < ql) return pii(-1, -1);
int mid = l + r >> 1;
pii mmax(-1, -1);
mmax = max(mmax, qry(ql, qr, now*2 , l, mid));
mmax = max(mmax, qry(ql, qr, now*2+1,mid+1,r));
pull(now);
return mmax;
}
int kth(int k, int now, int l, int r) {
push(now, r-l+1);
if (l == r) return l;
int mid = l + r >> 1;
int cL = (mid - l + 1) - arr[now].c;
if (k > cL) {
k -= cL;
int c = kth(k, now*2+1,mid+1,r);
pull(now);
return c;
} else {
int c = kth(k, now*2 , l, mid);
pull(now);
return c;
}
}
} seg;
int solve(int id, int N, int C, int R, int *K, int *S, int *E) {
vector <int> now;
for (int i = 0; i+1 < N; i++) {
if (now.size() == id) now.pb(R);
now.pb(K[i]);
}
if (now.size() == id) now.pb(R);
int cnt = 0;
seg.build(1, 0, N-1, now);
for (int i = 0; i < C; i++) {
int L = seg.kth(S[i], 1, 0, N-1);
int R = seg.kth(E[i], 1, 0, N-1);
auto [val, pos] = seg.qry(L, R, 1, 0, N-1);
if (val == R) cnt++;
seg.mdy(L, pos-1, 1, 0, N-1);
seg.mdy(pos+1, R, 1, 0, N-1);
}
return cnt;
}
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
pii ans = pii(0, 0);
for (int i = 0; i < N; i++)
ans = max(ans, pii(solve(i, N, C, R, K, S, E), -i));
return -ans.ss;
}
