#include <bits/stdc++.h>
using namespace std;
template <class T>
struct SegTree
{
T const identity;
std::vector <T> f;
T (* const combine)(T, T);
SegTree(int n, T const identity, T (* const combine)(T, T)) : identity(identity), f(n * 4, identity), combine(combine) {}
void init(int n, T val)
{
f.assign(n * 4, val);
}
template <class H>
void build(int x, int lo, int hi, const H construct)
{
if (lo == hi)
{
f[x] = construct(lo);
return;
}
int mid = (lo + hi) / 2;
build(x * 2, lo, mid, construct);
build(x * 2 + 1, mid + 1, hi, construct);
f[x] = combine(f[x * 2], f[x * 2 + 1]);
}
void set(int x, int lo, int hi, int idx, T val)
{
if (lo == hi)
{
f[x] = val;
return;
}
int mid = (lo + hi) / 2;
if (idx <= mid)
{
set(x * 2, lo, mid, idx, val);
}
else
{
set(x * 2 + 1, mid + 1, hi, idx, val);
}
f[x] = combine(f[x * 2], f[x * 2 + 1]);
}
void update(int x, int lo, int hi, int idx, T val)
{
if (lo == hi)
{
f[x] = combine(f[x], val);
return;
}
int mid = (lo + hi) / 2;
if (idx <= mid)
{
update(x * 2, lo, mid, idx, val);
}
else
{
update(x * 2 + 1, mid + 1, hi, idx, val);
}
f[x] = combine(f[x * 2], f[x * 2 + 1]);
}
T query(int x, int lo, int hi, int L, int R)
{
if (lo > R || hi < L)
{
return identity;
}
if (lo >= L && hi <= R)
{
return f[x];
}
int mid = (lo + hi) / 2;
return combine(query(x * 2, lo, mid, L, R), query(x * 2 + 1, mid + 1, hi, L, R));
}
};
int GetBestPosition(int n, int m, int K, int *a, int *S, int *E)
{
vector <int> f(n + 1);
auto update = [&](int x, int d)
{
for (; x <= n; x += x & -x)
{
f[x] += d;
}
};
auto kth = [&](int k) -> int
{
int pos = 0;
for (int mask = 1 << 20; mask; mask >>= 1)
{
if (pos + mask <= n && f[pos + mask] < k)
{
k -= f[pos += mask];
}
}
return ++pos;
};
for (int i = 1; i <= n; i++)
{
update(i, 1);
}
vector <array <int, 3>> rounds;
vector <int> sum(n + 1, 1);
for (int i = 0; i < m; i++)
{
S[i]++;
E[i]++;
int L = kth(S[i]), R = kth(E[i]);
R += sum[R] - 1;
for (int j = E[i]; j > S[i]; j--)
{
int pos = kth(j);
update(pos, -1);
sum[L] += sum[pos];
}
rounds.push_back({L, R, i});
}
vector <int> threats = {0};
for (int i = 0; i < n - 1; i++)
{
if (a[i] > K)
{
threats.push_back(i + 1);
}
}
threats.push_back(n);
sort(rounds.begin(), rounds.end());
int id = 0;
vector <int> alive(n + 1, 1e9);
SegTree <int> seg(n, 1e9, [](int x, int y) -> int
{
return (x < y ? x : y);
});
seg.init(n, 1e9);
for (int i = 1; i < (int)threats.size() - 1; i++)
{
while (id < (int)rounds.size() && rounds[id][0] <= threats[i])
{
seg.update(1, 1, n, rounds[id][1], rounds[id][2]);
id++;
}
for (int j = threats[i] + 1; j <= threats[i + 1]; j++)
{
alive[j] = min(alive[j], seg.query(1, 1, n, j, n));
}
}
sort(rounds.begin(), rounds.end(), [](array <int, 3> x, array <int, 3> y)
{
return x[1] > y[1];
});
id = 0;
seg.init(n, 1e9);
for (int i = (int)threats.size() - 3; ~i; i--)
{
while (id < (int)rounds.size() && rounds[id][1] >= threats[i + 1] + 1)
{
seg.update(1, 1, n, rounds[id][0], rounds[id][2]);
id++;
}
for (int j = threats[i] + 1; j <= threats[i + 1]; j++)
{
alive[j] = min(alive[j], seg.query(1, 1, n, 1, j));
}
}
vector <int> matches(n + 1);
vector <vector <int>> queries(m);
for (int i = 1; i <= n; i++)
{
if (alive[i] == 0)
{
matches[i] = 0;
}
else
{
queries[min(alive[i], m) - 1].push_back(i);
}
}
sort(rounds.begin(), rounds.end(), [](array <int, 3> x, array <int, 3> y)
{
return x[2] < y[2];
});
auto prefix = [&](int x)
{
int ans = 0;
for (; x > 0; x &= x - 1)
{
ans += f[x];
}
return ans;
};
f.assign(n + 1, 0);
for (int i = 0; i < m; i++)
{
update(rounds[i][0], 1);
update(rounds[i][1] + 1, -1);
for (auto &x: queries[i])
{
matches[x] = prefix(x);
}
}
int wins = -1, pos = -1;
for (int i = 1; i <= n; i++)
{
if (matches[i] > wins)
{
wins = matches[i];
pos = i - 1;
}
}
// cerr << "ranges\n";
// for (auto &x: rounds)
// {
// cerr << x[0] << " " << x[1] << "\n";
// }
// cerr << "number of wins\n";
// for (int i = 1; i <= n; i++)
// {
// cerr << matches[i] << " " << alive[i] << "\n";
// }
// cerr << "\n";
return pos;
}
