#include <stdio.h>
#define N 100000
#define N_ (1 << 17)
int st[N_ * 2], n_;
int get(int l, int k) {
int r = n_ - 1;
for (l += n_, r += n_; l <= r; l >>= 1, r >>= 1)
if ((l & 1) == 1) {
if (k >= st[l])
k -= st[l];
else {
while (l < n_)
if (k < st[l << 1 | 0])
l = l << 1 | 0;
else
k -= st[l << 1 | 0], l = l << 1 | 1;
return l - n_;
}
l++;
}
return n_;
}
void build(int n) {
int i;
for (i = 0; i < n; i++)
st[n_ + i] = 1;
for (i = n_ - 1; i > 0; i--)
st[i] = st[i << 1 | 0] + st[i << 1 | 1];
}
void remove_(int i) {
for (i += n_; i > 0; i >>= 1)
st[i]--;
}
int ft[N];
void update(int i, int n, int x) {
while (i < n) {
ft[i] += x;
i |= i + 1;
}
}
int query(int i) {
int x = 0;
while (i >= 0) {
x += ft[i];
i &= i + 1, i--;
}
return x;
}
int GetBestPosition(int n, int m, int r, int *aa, int *ll, int *rr) {
static int rr_[N];
int n1, h, i, k_, i_;
n_ = 1;
while (n_ < n)
n_ <<= 1;
build(n);
n1 = n;
for (h = 0; h < m; h++) {
ll[h] = get(0, ll[h]), rr[h] = (rr[h] == n1 - 1 ? n : get(0, rr[h] + 1)) - 1;
while ((i = get(ll[h] + 1, 0)) <= rr[h])
remove_(i);
n1 -= rr[h] - ll[h];
}
rr_[n - 1] = n - 1;
for (i = n - 2; i >= 0; i--)
rr_[i] = aa[i] > r ? i : rr_[i + 1];
build(n);
k_ = -1, i_ = -1;
for (h = 0; h < m; h++)
if (rr_[ll[h]] >= rr[h])
update(ll[h], n, 1), update(rr[h] + 1, n, -1);
else
while ((i = get(ll[h], 0)) <= rr[h]) {
int k = query(i);
if (k_ < k || k_ == k && i_ > i)
k_ = k, i_ = i;
remove_(i);
}
return i_;
}
