#include <bits/stdc++.h>
#define pb push_back
using namespace std;
const int N = (1 << 18);
int nDebuts[N * 2];
int cumul[N];
bool onGagne(int fin, int deb){
int sum = cumul[fin];
if (deb > 0)
sum -= cumul[deb - 1];
return (sum == 0);
}
int getSum(int gauche, int droite){
if (gauche > droite)
return 0;
if (gauche%2 == 1)
return nDebuts[gauche] + getSum(gauche + 1, droite);
if (droite%2 == 0)
return nDebuts[droite] + getSum(gauche, droite - 1);
return getSum(gauche / 2, droite / 2);
}
struct Noeud {
int ajout;
bool estMort;
void mourir(){
estMort = true;
}
void ajouter(int delta){
if (!estMort)
ajout += delta;
}
};
Noeud arbre[N * 2];
void push(int noeud){
for (int enfant = noeud * 2; enfant <= noeud * 2 + 1; enfant++){
arbre[enfant].ajouter(arbre[noeud].ajout);
if (arbre[noeud].estMort)
arbre[enfant].mourir();
}
arbre[noeud].ajout = 0;
}
void update(int noeud, int curl, int curr, int reql, int reqr, int typeOp){
if (curl > reqr || reql > curr)
return;
if (reql <= curl && curr <= reqr){
if (typeOp == 0)
arbre[noeud].mourir();
else if (typeOp == 1)
arbre[noeud].ajouter(1);
return;
}
push(noeud);
int milieu = (curl + curr)/2;
update(noeud * 2, curl, milieu, reql, reqr, typeOp);
update(noeud * 2 + 1, milieu + 1, curr, reql, reqr, typeOp);
}
int GetBestPosition(int nGars, int nRounds, int rangPaume, int *rangs, int *gauche, int *droite) {
for (int iRound = 0; iRound < nRounds; ++iRound){
int compression = droite[iRound] - gauche[iRound];
gauche[iRound] += getSum(N, N + gauche[iRound] - 1);
droite[iRound] += getSum(N, N + droite[iRound]);
for (int noeud = N + gauche[iRound]; noeud > 0; noeud /= 2)
nDebuts[noeud] += compression;
}
/*
for (int iRound = 0; iRound < nRounds; ++iRound)
cout << "inter " << gauche[iRound] << " " << droite[iRound] << endl;
*/
for (int ind = 0; ind < nGars - 1; ++ind){
cumul[ind] = (rangs[ind] > rangPaume);
if (ind != 0)
cumul[ind] += cumul[ind - 1];
}
for (int iRound = 0; iRound < nRounds; ++iRound)
update(1, 0, N - 1, gauche[iRound], droite[iRound] - 1, onGagne(gauche[iRound], droite[iRound]));
int iOpt = -1;
for (int ind = 0; ind < nGars - 1; ++ind){
update(1, 0, N - 1, ind, ind, 2);
if (iOpt == -1 || arbre[N + iOpt].ajout < arbre[N + ind].ajout)
iOpt = ind;
}
return iOpt;
}
