#include <iostream>
using namespace std;
const int maxn = 100005;
int n, q;
int my_rank;
int a[maxn];
pair<int, int> queries[maxn];
int tree[4 * maxn];
int lazy[4 * maxn];
void build(int node, int l, int r)
{
if (l == r)
{
tree[node] = 1;
return;
}
int mid = (l + r) / 2;
build(2 * node, l, mid);
build(2 * node + 1, mid + 1, r);
tree[node] = tree[2 * node] + tree[2 * node + 1];
}
void push_lazy(int node, int l, int r)
{
if (lazy[node] == 0)
{
return;
}
tree[node] = 0;
if (l != r)
{
lazy[2 * node] = 1;
lazy[2 * node + 1] = 1;
}
lazy[node] = 0;
}
void update(int node, int l, int r, int ql, int qr)
{
push_lazy(node, l, r);
if (l > qr || r < ql)
{
return;
}
if (ql <= l && r <= qr)
{
lazy[node] = 1;
push_lazy(node, l, r);
return;
}
int mid = (l + r) / 2;
update(2 * node, l, mid, ql, qr);
update(2 * node + 1, mid + 1, r, ql, qr);
tree[node] = tree[2 * node] + tree[2 * node + 1];
}
int query(int node, int l, int r, int ql, int qr)
{
push_lazy(node, l, r);
if (l > qr || r < ql)
{
return 0;
}
if (ql <= l && r <= qr)
{
return tree[node];
}
int mid = (l + r) / 2;
return query(2 * node, l, mid, ql, qr) + query(2 * node + 1, mid + 1, r, ql, qr);
}
int tree2[4 * maxn];
void build2(int node, int l, int r)
{
if (l == r)
{
tree2[node] = a[l];
return;
}
int mid = (l + r) / 2;
build2(2 * node, l, mid);
build2(2 * node + 1, mid + 1, r);
tree2[node] = max(tree2[2 * node], tree2[2 * node + 1]);
}
int query2(int node, int l, int r, int ql, int qr)
{
if (l > qr || r < ql)
{
return -1;
}
if (ql <= l && r <= qr)
{
return tree2[node];
}
int mid = (l + r) / 2;
return max(query2(2 * node, l, mid, ql, qr), query2(2 * node + 1, mid + 1, r, ql, qr));
}
int intervals[maxn];
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E)
{
n = N;
q = C;
if (n == 1)
{
return 0;
}
my_rank = R + 1;
for (int i = 0; i < n - 1; ++i)
{
a[i + 1] = K[i] + 1;
}
for (int i = 0; i < q; ++i)
{
queries[i + 1] = make_pair(S[i] + 1, E[i] + 1);
}
build(1, 1, n);
build2(1, 1, n - 1);
for (int i = 1; i <= q; ++i)
{
int ql, qr;
int l = 1;
int r = n;
while (l <= r)
{
int mid = (l + r) / 2;
if (query(1, 1, n, 1, mid) < queries[i].first)
{
l = mid + 1;
}
else
{
r = mid - 1;
}
}
ql = l;
l = 1;
r = n;
while (l <= r)
{
int mid = (l + r) / 2;
if (query(1, 1, n, 1, mid) <= queries[i].second)
{
l = mid + 1;
}
else
{
r = mid - 1;
}
}
qr = r;
if (my_rank > query2(1, 1, n - 1, ql, qr - 1))
{
++intervals[ql];
--intervals[qr + 1];
}
if (ql < qr)
{
update(1, 1, n, ql + 1, qr);
}
}
int best = 0;
for (int i = 1; i <= n; ++i)
{
intervals[i] += intervals[i - 1];
best = max(best, intervals[i]);
}
for (int i = 1; i <= n; ++i)
{
if (intervals[i] == best)
{
return i - 1;
}
}
return -1;
}
