#include <stdio.h>
#include <algorithm>
#include <vector>
#define INF 0x7fffffff
using namespace std;
typedef pair <int,int> ppair;
typedef pair <int,ppair> pppair;
static vector <pppair> A;
static int M, Idx[2621044], Left[1000000], Stack[500000][3], Top, Ans=-1, AnsLoc, Lb, Rb, Value;
int FindLoc(int Num) {
int Loc=1;
while(Loc<M) {
Loc*=2;
if(Num>Idx[Loc]) {
Num-=Idx[Loc];
Loc++;
}
}
return Loc;
}
void ReNew(int X, int Y) {
int i, Loc=Left[Y-M], Temp;
Left[Y-M]=Left[X-M];
while(1) {
Temp=Loc;
while(Temp) {
Idx[Temp]--;
Temp/=2;
}
Temp=Left[Loc-M];
Left[Loc-M]=0;
if(Loc==X)
break;
Loc=Temp;
}
}
void IdxTree(int LL, int RR, int Now) {
int Mid=(LL+RR)/2;
if(Lb<=LL && RR<=Rb)
Value&=Idx[Now];
else {
if(Lb<=Mid)
IdxTree(LL,Mid,2*Now);
if(Mid+1<=Rb)
IdxTree(Mid+1,RR,2*Now+1);
}
}
int OK(int LeftBound, int RightBound) {
Lb=LeftBound;
Rb=RightBound;
Value=1;
if(Lb<=Rb)
IdxTree(0,M-1,1);
return Value;
}
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
int i, X, Y, Size;
for(M=1 ; M<N ; M*=2);
for(i=M ; i<2*M ; i++) {
Idx[i]=1;
Left[i-M]=i-1;
}
for(i=M-1 ; i>=1 ; i--)
Idx[i]=Idx[2*i]+Idx[2*i+1];
for(i=0 ; i<C ; i++) {
X=FindLoc(S[i]+1);
Y=FindLoc(E[i]+1);
S[i]=Left[X-M]+1-M;
E[i]=Y-M;
ReNew(X,Y);
}
for(i=M ; i<M+N ; i++) {
if(K[i-M]<R)
Idx[i]=1;
else
Idx[i]=0;
}
for(i=M-1 ; i>=1 ; i--)
Idx[i]=Idx[2*i]&Idx[2*i+1];
for(i=0 ; i<C ; i++) {
A.push_back(make_pair(S[i],make_pair(-E[i],-1)));
A.push_back(make_pair(E[i],make_pair(-S[i],1)));
}
for(i=0 ; i<N ; i++) {
A.push_back(make_pair(i,make_pair(-i,-1)));
A.push_back(make_pair(i,make_pair(-i,1)));
}
sort(A.begin(),A.end());
Size=A.size();
for(i=0 ; i<Size ; i++) {
if(A[i].second.second==-1) {
Top++;
Stack[Top][0]=A[i].first;
Stack[Top][1]=-INF;
}
else {
if(Stack[Top][0]==A[i].first) {
Stack[Top][1]=0;
Stack[Top][2]=A[i].first;
}
if(OK(Stack[Top][0],A[i].first-1)) {
if(Ans<Stack[Top][1]) {
Ans=Stack[Top][1];
AnsLoc=Stack[Top][2];
}
if(Stack[Top-1][1]<Stack[Top][1]+1) {
Stack[Top-1][1]=Stack[Top][1]+1;
Stack[Top-1][2]=Stack[Top][2];
}
}
Top--;
}
}
return AnsLoc;
}
