#include <bits/stdc++.h>
#define pb push_back
using namespace std;
const int N = (1 << 18);
int nDebuts[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);
}
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);
}
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;
// 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;
}
