/*
______ _____ _______ _ _ _______ __ _ _____ _ _ _
|_____/ | | | |____/ |______ | \ | | | | | |
| \_ |_____| |_____ | \_ ______| | \_| |_____| |__|__|
. . . . . .
_\/ \/_ _\/ \/_ _\/ \/_
_\/\/_ _\/\/_ _\/\/_
_\_\_\/\/_/_/_ _\_\_\/\/_/_/_ _\_\_\/\/_/_/_
/ /_/\/\_\ \ / /_/\/\_\ \ / /_/\/\_\ \
_/\/\_ _/\/\_ _/\/\_
/\ /\ /\ /\ /\ /\
' ' ' ' ' '
*/
#pragma GCC optimize ("O3")
#pragma GCC target ("avx2")
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <climits>
#include <cstdint>
#include <cmath>
#include <chrono>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_set>
#include <unordered_map>
#include <vector>
using namespace std;
struct Node {
int val;
int weight, size;
Node *left, *right;
Node(int c) : val(c), weight(rand()), size(1), left(NULL), right(NULL) {}
};
inline int size(Node *treap) { return treap ? treap->size : 0; }
void split(Node *treap, Node *&left, Node *&right, int val) {
if (!treap) {
left = right = NULL;
return;
}
if (size(treap->left) < val) {
split(treap->right, treap->right, right, val - size(treap->left) - 1);
left = treap;
} else {
split(treap->left, left, treap->left, val);
right = treap;
}
treap->size = 1 + size(treap->left) + size(treap->right);
}
void merge(Node *&treap, Node *left, Node *right) {
if (left == NULL) {
treap = right;
return;
}
if (right == NULL) {
treap = left;
return;
}
if (left->weight < right->weight) {
merge(left->right, left->right, right);
treap = left;
} else {
merge(right->left, left, right->left);
treap = right;
}
treap->size = 1 + size(treap->left) + size(treap->right);
}
ostream &operator<<(ostream &os, Node *n) {
if (!n) return os;
os << n->left;
os << n->val;
os << n->right;
return os;
}
void get(Node *n, vector<int> &v){
if(!n) return;
v.push_back(n->val);
get(n->left, v);
get(n->right, v);
}
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
int ans=-1;
int best=-1;
Node *root=NULL;
for(int i=0; i<N; i++){
merge(root, root, new Node(i));
}
vector<int> next(N+C, 0);
for(int j=0; j<C; j++){
vector<int> atual;
Node *a, *b, *c;
split(root, a, b, S[j]);
split(b, b, c, E[j]-S[j]+1);
//cout<<a<<' '<<b<<' '<<c<<'\n';
get(b, atual);
delete(b);
for(int u: atual){
next[u]=N+j;
}
merge(root, a, new Node(N+j));
merge(root, root, c);
//cout<<root<<'\n';
}
vector<int> arvore(N+C);
for(int pos=0; pos<N; pos++){
arvore.assign(N+C, -1);
for(int i=0; i<N; i++){
if(i<pos){
arvore[i]=K[i];
}else if(i==pos){
arvore[i]=R;
}else{
arvore[i]=K[i-1];
}
}
for(int i=0; i<N+C-1; i++){
arvore[next[i]]=max(arvore[next[i]], arvore[i]);
}
int cur=0;
for(int i=N; i<N+C; i++){
if(arvore[i]==R) cur++;
}
if(cur>best){
best=cur;
ans=pos;
}
}
return ans;
}
