// ~ Be Name Khoda ~ //
#include <bits/stdc++.h>
//#pragma GCC optimize ("O3")
//#pragma GCC target("avx2")
//#pragma GCC optimize("unroll-loops,Ofast")
using namespace std;
typedef long long ll;
#define pb push_back
#define mp make_pair
#define all(x) x.begin(), x.end()
#define fi first
#define se second
const int maxn = 1e6 + 10;
const int maxn5 = 5e5 + 10;
const int maxnt = 1.2e6 + 10;
const int maxn3 = 1e3 + 10;
const int mod = 1e9 + 7;
const ll inf = 1e18;
int GetBestPosition(int n, int c, int r, int *k, int *s, int *e){
for(int i = 0; i < n - 1; i++)
k[i] = (k[i] > r);
int pre = -1, nxt = 0;
while(nxt < n - 1 && !k[nxt])
nxt++;
int mx = 0, out = 0;
for(int i = 0; i < n; i++){
if(i > nxt){
pre = nxt;
nxt++;
while(nxt < n - 1 && !k[nxt])
nxt++;
}
int keepnxt = nxt, keeppre = pre;
int l = max(0, pre), r = max(0, n - nxt - 2), pos = i, have = 0;
nxt++;
for(int j = 0; j < c; j++){
//cout << "in " << j << ' ' << s[j] << ' ' << e[j] << ' ' << l << ' ' << r << ' ' << pos << ' ' << pre << ' ' << nxt << endl;
if(e[j] <= pre){
l -= e[j] - s[j];
pre -= e[j] - s[j];
nxt -= e[j] - s[j];
pos -= e[j] - s[j];
}
else if(s[j] >= nxt)
r -= e[j] - s[j];
else if(s[j] <= pos && pos <= e[j]){
if(s[j] <= pre || nxt <= e[j])
break;
have++;
nxt -= e[j] - s[j];
pos = s[j];
}
else if(e[j] < pos){
int vall = max(0, pre - s[j]);
l -= vall;
pre -= vall;
pos -= e[j] - s[j];
nxt -= e[j] - s[j];
}
else{
int valr = max(0, e[j] - nxt);
r -= valr;
nxt -= e[j] - s[j] - valr;
}
}
pre = keeppre;
nxt = keepnxt;
if(have > mx){
mx = have;
out = i;
}
//cout << i << ' ' << have << endl;
}
return out;
}
