#include <bits/stdc++.h>
#define pb push_back
using namespace std;
const int N = (1 << 18);
int nPartis[N * 2];
int cumul[N], res[N];
bool onGagne(int fin, int deb){
int sum = cumul[fin];
if (deb > 0)
sum -= cumul[deb - 1];
return (sum == 0);
}
void partir(int ind, int delta){
for (int noeud = N + ind; noeud > 0; noeud /= 2)
nPartis[noeud] += delta;
}
int getKth(int noeud, int tailleInter, int k){ //Le 1 est le premier
if (noeud >= N)
return noeud - N;
int nGauche = tailleInter/2 - nPartis[noeud * 2];
if (k > nGauche)
return getKth(noeud * 2 + 1, tailleInter/2, k - nGauche);
return getKth(noeud * 2, tailleInter/2, k);
}
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] = getKth(1, N, gauche[iRound]);
droite[iRound] += getKth(1, N, droite[iRound]);
for (int noeud = N + gauche[iRound]; noeud > 0; noeud /= 2)
nPartis[noeud] += compression;
// 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){
if (onGagne(gauche[iRound], droite[iRound])){
res[gauche[iRound]]++;
res[droite[iRound] + 1]--;
}
}
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;
}
