#include <bits/stdc++.h>
using namespace std;
const int N = 5000;
struct Node
{
Node* next;
int l;
int r;
Node(int l1, int r1)
{
l = l1;
r = r1;
next = nullptr;
}
};
vector<int> pref;
int go(Node* cur)
{
int sum = pref[cur->r];
if (cur->l != 0) sum -= pref[cur->l - 1];
if (sum != 0) return 0;
int res = 1;
if (cur->next != nullptr) res += go(cur->next);
return res;
}
Node* first[N];
int GetBestPosition(int n, int c, int r, int *k, int *s, int *e) {
for (int i = 0; i < n; i++)
{
first[i] = new Node(i, i);
}
vector<Node*> cur(first, first + N);
for (int i = 0; i < c; i++)
{
Node* next = new Node(cur[s[i]]->l, cur[e[i]]->r);
for (int l = s[i]; l <= e[i]; l++)
{
cur[l]->next = next;
}
cur.erase(cur.begin() + s[i], cur.begin() + e[i] + 1);
cur.insert(cur.begin() + s[i], next);
}
int pos = -1;
int best = -1;
for (int i = 0; i < n; i++)
{
vector<int> order(n);
pref.resize(n);
pref.clear();
order[i] = r;
for (int j = 0; j < n - 1; j++)
{
if (j < i) order[j] = k[j];
else order[j + 1] = k[j];
}
for (int j = 0; j < n; j++)
{
if (order[j] <= r) order[j] = 0;
else order[j] = 1;
}
pref[0] = order[0];
for (int i = 1; i < n; i++)
{
pref[i] += pref[i - 1] + order[i];
}
int cres = go(first[i]) - 1;
if (cres > best)
{
best = cres;
pos = i;
}
}
return pos;
}
/*
5 3 2
1
0
4
3
0 1
0 1
0 2
*/
