#include <bits/stdc++.h>
#define pb push_back
using namespace std;
const int N = (1 << 18), OO = 1e9;
struct Noeud {
int mini, maxi, a, b;
int deb, fin;
void affine(int na, int nb){
a *= na;
b = b * na + nb;
mini = mini * na + nb;
maxi = maxi * na + nb;
}
};
Noeud arbre[N * 2];
int cumul[N], res[N];
bool onGagne(int deb, int fin){
int sum = cumul[fin];
if (deb > 0)
sum -= cumul[deb];
return (sum == 0);
}
void push(int noeud){
for (int enfant = noeud * 2; enfant <= noeud * 2 + 1; ++enfant)
arbre[enfant].affine(arbre[noeud].a, arbre[noeud].b);
arbre[noeud].a = 1, arbre[noeud].b = 0;
}
int getKth(int noeud, int k){
if (noeud >= N)
return noeud - N;
push(noeud);
if (arbre[noeud * 2].maxi >= k)
return getKth(noeud * 2, k);
return getKth(noeud * 2 + 1, k);
}
int getMax(int noeud, int reql, int reqr, int a, int b){
if (arbre[noeud].fin <= reql || reqr <= arbre[noeud].deb)
return -OO;
if (reql <= arbre[noeud].deb && arbre[noeud].fin <= reqr){
arbre[noeud].affine(a, b);
return arbre[noeud].maxi;
}
push(noeud);
int maxl = getMax(noeud * 2, reql, reqr, a, b), maxr = getMax(noeud * 2 + 1, reql, reqr, a, b);
arbre[noeud].mini = min(arbre[noeud * 2].mini, arbre[noeud * 2 + 1].mini);
arbre[noeud].maxi = max(arbre[noeud * 2].maxi, arbre[noeud * 2 + 1].maxi);
return max(maxl, maxr);
}
int GetBestPosition(int nGars, int nRounds, int rangPaume, int *rangs, int *gauche, int *droite) {
for (int ind = N; ind < 2 * N; ++ind)
arbre[ind] = {ind - N, ind - N, 1, 0, ind - N, ind - N + 1};
for (int ind = N - 1; ind > 0; --ind)
arbre[ind] = {arbre[ind * 2].mini, arbre[ind * 2 + 1].maxi, 1, 0, arbre[ind * 2].deb, arbre[ind * 2 + 1].fin};
for (int iRound = 0; iRound < nRounds; ++iRound){
int ng = getKth(1, gauche[iRound]), nd = getKth(1, droite[iRound] + 1);
int pref = getMax(1, ng, ng + 1, 1, 0);
getMax(1, ng, nd, 0, pref);
getMax(1, nd, N, 1, -(droite[iRound] - gauche[iRound]));
gauche[iRound] = ng;
droite[iRound] = nd;
// cout << "t" << gauche[iRound] << " " << droite[iRound] << endl;
}
cumul[0] = 0;
for (int ind = 1; ind < nGars; ++ind){
cumul[ind] = (rangs[ind - 1] > rangPaume) + cumul[ind - 1];
// cout << cumul[ind] << " ";
}
//cout << endl;
for (int iRound = 0; iRound < nRounds; ++iRound){
// cout << "t" << gauche[iRound] << " " << droite[iRound] << endl;
if (onGagne(gauche[iRound] + 1, droite[iRound] - 1)){
res[gauche[iRound]]++;
res[droite[iRound]]--;
}
}
int iOpt = 0;
//cout << "res " << res[0] << " ";
for (int ind = 1; ind < nGars; ++ind){
res[ind] += res[ind - 1];
// cout << res[ind] << " ";
if (res[ind] > res[iOpt])
iOpt = ind;
}
//cout << endl;
return iOpt;
}
