#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll INF = 1e9+7;
ll MOD = 998244353;
typedef pair<ll,ll> ii;
#define iii pair<ll,ii>
#define f(i,a,b) for(ll i = a;i < b;i++)
#define pb push_back
#define vll vector<ll>
#define F first
#define S second
#define all(x) (x).begin(), (x).end()
///I hope I will get uprating and don't make mistakes
///I will never stop programming
///sqrt(-1) Love C++
///Please don't hack me
///@TheofanisOrfanou Theo830
///Think different approaches (bs,dp,greedy,graphs,shortest paths,mst)
///Stay Calm
///Look for special cases
///Beware of overflow and array bounds
///Think the problem backwards
///Training
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
uniform_int_distribution<ll> distr;
ll rnd(ll a, ll b){return distr(rng)%(b-a+1)+a;}
/*
#define inbuf_len 1 << 16
#define outbuf_len 1 << 16
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E);
int main() {
int tmp;
char *inbuf, *outbuf;
inbuf = (char*) malloc(inbuf_len * sizeof(char));
outbuf = (char*) malloc(outbuf_len * sizeof(char));
tmp = setvbuf(stdin, inbuf, _IOFBF, inbuf_len);
assert(tmp == 0);
tmp = setvbuf(stdout, outbuf, _IOFBF, outbuf_len);
assert(tmp == 0);
int N, C, R;
int *K, *S, *E;
tmp = scanf("%d %d %d", &N, &C, &R);
assert(tmp == 3);
K = (int*) malloc((N-1) * sizeof(int));
S = (int*) malloc(C * sizeof(int));
E = (int*) malloc(C * sizeof(int));
int i;
for (i = 0; i < N-1; i++) {
tmp = scanf("%d", &K[i]);
assert(tmp == 1);
}
for (i = 0; i < C; i++) {
tmp = scanf("%d %d", &S[i], &E[i]);
assert(tmp == 2);
}
printf("%d\n", GetBestPosition(N, C, R, K, S, E));
return 0;
}
*/
ll pre[100005] = {0};
ll sum(ll l,ll r){
return pre[r+1] - pre[l];
}
struct node{
ll sum = 0,lazy = 0;
};
node seg[400005],seg2[400005];
void build(ll s,ll e,ll idx){
if(s == e){
seg[idx].sum = 1;
return;
}
ll mid = (s+e)/2;
build(s,mid,idx*2);
build(mid+1,e,idx*2+1);
seg[idx].sum = seg[idx*2].sum + seg[idx*2+1].sum;
}
void update(ll s,ll e,ll qs,ll qe,ll idx){
if(qs <= s && e <= qe){
seg[idx].lazy = 1;
seg[idx].sum = 0;
return;
}
else if(s > qe || e < qs){
return;
}
if(seg[idx].lazy == 1){
seg[idx].lazy = 0;
seg[idx*2].sum = seg[idx*2+1].sum = 0;
seg[idx*2].lazy = seg[idx*2+1].lazy = 1;
}
ll mid = (s+e)/2;
update(s,mid,qs,qe,idx*2);
update(mid+1,e,qs,qe,idx*2+1);
seg[idx].sum = seg[idx*2].sum + seg[idx*2+1].sum;
}
void upd(ll s,ll e,ll qs,ll qe,ll idx){
if(qs <= s && e <= qe){
seg2[idx].lazy++;
seg2[idx].sum += (e - s + 1);
return;
}
else if(s > qe || e < qs){
return;
}
ll mid = (s+e)/2;
seg2[idx*2].sum += seg2[idx].lazy * (mid - s + 1);
seg2[idx*2+1].sum += seg2[idx].lazy * (e - mid);
seg2[idx*2].lazy += seg2[idx].lazy;
seg2[idx*2+1].lazy += seg2[idx].lazy;
seg2[idx].lazy = 0;
upd(s,mid,qs,qe,idx*2);
upd(mid+1,e,qs,qe,idx*2+1);
seg2[idx].sum = seg2[idx*2].sum + seg2[idx*2+1].sum;
}
ll ask(ll s,ll e,ll qs,ll qe,ll idx){
if(qs <= s && e <= qe){
return seg2[idx].sum;
}
else if(s > qe || e < qs){
return 0;
}
ll mid = (s+e)/2;
seg2[idx*2].sum += seg2[idx].lazy * (mid - s + 1);
seg2[idx*2+1].sum += seg2[idx].lazy * (e - mid);
seg2[idx*2].lazy += seg2[idx].lazy;
seg2[idx*2+1].lazy += seg2[idx].lazy;
seg2[idx].lazy = 0;
ll a = ask(s,mid,qs,qe,idx*2);
ll b = ask(mid+1,e,qs,qe,idx*2+1);
return a + b;
}
ll query(ll s,ll e,ll k,ll idx){
if(s == e){
return s-1;
}
if(seg[idx].lazy == 1){
seg[idx].lazy = 0;
seg[idx*2].sum = seg[idx*2+1].sum = 0;
seg[idx*2].lazy = seg[idx*2+1].lazy = 1;
}
ll mid = (s+e)/2;
if(seg[idx*2].sum >= k){
return query(s,mid,k,idx*2);
}
else{
return query(mid+1,e,k - seg[idx*2].sum,idx*2+1);
}
}
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
ll posa = 0;
ll ans = 0;
f(i,0,N-1){
pre[i+1] = pre[i] + (K[i] > R);
}
ll n = N+1;
build(1,n,1);
f(i,0,C){
S[i] = query(1,n,S[i]+1,1);
E[i] = query(1,n,E[i]+2,1) - 1;
update(1,n,S[i]+2,E[i]+1,1);
}
f(j,0,C){
if(sum(S[j],E[j]-1) == 0){
upd(1,n,S[j]+1,E[j]+1,1);
}
}
f(i,0,n){
ll res = ask(1,n,i+1,i+1,1);
if(res > posa){
posa = res;
ans = i;
}
}
return ans;
}
/*
5 3 3
1
0
2
4
1 3
0 1
0 1
*/
