#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<pair<int, int>, null_type,less<pair<int, int>>, rb_tree_tag,tree_order_statistics_node_update>
struct node
{
int d, l, r, maxi, maxlast, i;
node(int D = -1, int L = -1, int R = -1, int MAXI = -1, int MAXLAST = -1, int I = -1): d(D), l(L), r(R), maxi(MAXI), maxlast(MAXLAST), i(I) {}
};
void upd(node &a, const node &b)
{
if (b.d > a.d || (a.d == b.d && b.i < a.i)) a.d = b.d, a.i = b.i;
}
int GetBestPosition(int n, int m, int nw, int *k, int *l, int *r)
{
ordered_set s;
vector<node> v;
for (int i = 0; i < n - 1; i++) v.push_back(node(0, i, i, k[i], 0, i)), s.insert({i, i});
node best; best.i = 0;
for (int i = 0; i < m; i++)
{
node now;
int len = r[i] - l[i] + 1;
for (int j = 0; j < len; j++)
{
auto it = s.find_by_order(l[i]);
node nj = v[it->second];
now.maxi = max(now.maxi, nj.maxi);
if (j == 0) now.l = nj.l;
if (j == len-1) now.r = nj.r, now.maxlast = max(now.maxlast, nj.maxlast);
else now.maxlast = max(now.maxlast, nj.maxi);
upd(now, nj);
s.erase(it);
}
now.d++;
if (now.maxlast < nw)
upd(best, now);
v.push_back(now);
s.insert({now.l, v.size() - 1});
}
return best.i;
}
