#include <bits/stdc++.h>
using namespace std;
const int nmax = 1e5 + 5;
int n;
struct Aib {
int v[nmax + 1];
int lsb (int x) {
return x & -x;
}
void update (int pos, int val) {
for (int i = pos + 1; i <= n; i += lsb(i))
v[i] += val;
}
int query (int cnt) {
int ans = 0;
++ cnt;
for (int i = (1 << 18); i > 0; i >>= 1) {
if (ans + i <= n && v[ans + i] < cnt) {
cnt -= v[ans + i];
ans += i;
}
}
return ans;
}
} aib;
static set<pair<int, int>> s;
static int st[nmax + 1], dr[nmax + 1];
static vector<pair<int, int>> ord;
static int inchide[nmax + 1];
bool cmp (pair<int, int> a, pair<int, int> b) {
if (a.first != b.first)
return a.first < b.first;
return a.second > b.second;
}
void precalc (int N, int C, int *S, int *E) {
for (int i = 0; i < N; ++ i) {
s.insert({i, i});
aib.update(i, 1);
}
for (int i = 0; i < C; ++ i) {
int start = aib.query(S[i]);
int stop = -1;
set<pair<int, int>>::iterator it = s.lower_bound({start, start});
assert(it -> first == start);
for (int j = S[i]; j <= E[i]; ++ j) {
stop = it -> second;
aib.update(it -> first, -1);
set<pair<int, int>>::iterator aux = it;
++ aux;
s.erase(it);
it = aux;
}
ord.push_back({start, stop});
++ inchide[stop];
s.insert({start, stop});
aib.update(start, 1);
}
sort(ord.begin(), ord.end(), cmp);
}
static pair<int, int> stv[nmax + 1];
bool check (int pos, pair<int, int> intv) {
if (pos - 1 >= 0 && intv.first <= st[pos - 1])
return 0;
if (pos < n - 1 && dr[pos] + 1 <= intv.second)
return 0;
return 1;
}
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
n = N;
for (int i = 0; i < N - 1; ++ i) {
st[i] = -1;
if (K[i] > R)
st[i] = i;
else if (i - 1 >= 0)
st[i] = st[i - 1];
}
for (int i = N - 2; i >= 0; -- i) {
dr[i] = N;
if (K[i] > R)
dr[i] = i;
else if (i + 1 < N - 1)
dr[i] = dr[i + 1];
}
// precalc starile de paranteze
precalc(N, C, S, E);
int ans = -1, pos = -1;
int ind = 0;
int top = 0;
for (int i = 0; i < N; ++ i) {
while (ind < ord.size() && ord[ind].first == i)
stv[++ top] = ord[ind ++];
// caut binar cat rezista
int sol = top + 1;
for (int step = (1 << 18); step > 0; step >>= 1) {
if (sol - step > 0 && check(i, stv[sol - step])) {
sol -= step;
}
}
int r = top - sol + 1;
if (r > ans) {
ans = r;
pos = i;
}
for (int j = 0; j < inchide[i]; ++ j)
-- top;
}
return pos;
}
