#pragma once
#include <iostream>
using namespace std;
struct SegmentTree
{
int mx=-1;
int s,e;
SegmentTree* next[2];
SegmentTree(int l,int r)
{
s=l;
e=r;
if(s!=e)
{
int mid=(s+e)/2;
next[0]=new SegmentTree(s,mid);
next[1]=new SegmentTree(mid+1,e);
}
}
void Update(int& i,int& x)
{
if(i<s or e<i)
return ;
if(s==e)
{
mx=x;
return;
}
next[0]->Update(i,x);
next[1]->Update(i,x);
mx=max(next[0]->mx,next[1]->mx);
}
int get(int& l,int& r)
{
if(r<s or e<l)
return -1;
if(l<=s and e<=r)
{
return mx;
}
return max(next[0]->get(l,r),next[1]->get(l,r));
}
};
//for an i : Who is representing this index and whom is this index representing
int GetBestPosition(int n, int c, int r, int k[], int s[], int e[])
{
// Lets change the queries from the changed array to the original array
int cs[c],ce[c];
{
int a[n],mi[n],mx[n];
for(int i=0;i<n;i++)
a[i]=mi[i]=mx[i]=i;
int len=n;
for(int ro=0;ro<c;ro++)
{
int ns=a[s[ro]];
int ne=a[e[ro]];
for(int l=s[ro];l<=e[ro];l++)
{
ns=min(ns,mi[a[l]]);
ne=max(ne,mx[a[l]]);
}
for(int l=s[ro];l<=e[ro];l++)
{
mi[a[l]]=min(ns,mi[a[l]]);
mx[a[l]]=max(ne,mx[a[l]]);
}
for(int j=e[ro];j<len;j++)
a[j+s[ro]-e[ro]]=a[j];
len=len-e[ro]+s[ro];
cs[ro]=ns;
ce[ro]=ne;
}
}
int wins=0;
int poss=0;
SegmentTree* st=new SegmentTree(0,n-1);
int a[n];
for(int p=0;p<(n-1);p++)
{
int win=0;
for(int j=0;j<p;j++)
a[j]=k[j];
a[p]=r;
for(int j=p;j<(n-1);j++)
a[j+1]=k[j];
for(int lk=0;lk<n;lk++)
st->Update(lk,a[lk]);
for(int round=0;round<c;round++)
{
int mx=st->get(cs[round],ce[round]);
if(mx==r)
win++;
}
if(wins<win)
{
wins=win;
poss=p;
}
}
return poss;
}
