#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define fi first
#define se second
#define mp make_pair
vector<int> ord;
const int N = (int)2e5 + 10;
struct Node{
int cnt;
int lazy;
};
Node T[N * 4 + 512];
int id[N];
void build(int node, int cl, int cr){
T[node].cnt = cr - cl + 1;
if(cl == cr)
return;
int mid = (cl + cr) / 2;
build(node * 2, cl, mid);
build(node * 2 + 1, mid + 1, cr);
}
int n;
void push(int node, int cl, int cr){
if(T[node].lazy){
T[node].cnt=0;
if(cl != cr){
T[node * 2].lazy = 1;
T[node * 2 + 1].lazy = 1;
}
T[node].lazy = 0;
}
}
void reset(int node, int cl, int cr, int tl, int tr){
push(node, cl, cr);
if(cr < tl || cl > tr) return;
if(cl >= tl && cr <= tr){
T[node].lazy = 1;
push(node, cl, cr);
return;
}
int mid = (cl + cr) / 2;
reset(node * 2, cl, mid, tl, tr);
reset(node * 2 + 1, mid + 1, cr, tl, tr);
T[node].cnt = T[node * 2].cnt + T[node * 2 + 1].cnt;
}
int get(int node, int cl, int cr, int p){
if(cl == cr){
return cl;
}
int mid = (cl + cr) / 2;
push(node * 2, cl, mid);
push(node * 2 + 1, mid + 1, cr);
T[node].cnt = T[node * 2].cnt + T[node * 2 + 1].cnt;
if(T[node * 2].cnt >= p)
return get(node * 2, cl, mid, p);
else
return get(node * 2 + 1, mid + 1, cr, p - T[node * 2].cnt);
}
const int LOG = 18;
int par[LOG][N];
pii segm[N];
int high[N * 2];
void upd(int iq, int v){
iq += n;
high[iq] = v;
iq /= 2;
while(iq > 0){
high[iq] = max(high[iq * 2], high[iq * 2 + 1]);
iq /= 2;
}
}
int get_high(int li, int ri){
li += n;
ri += n;
int res = -1;
while(li <= ri){
if(li % 2 == 1) res = max(res, high[li ++ ]);
if(ri % 2 == 0) res = max(res, high[ri -- ]);
li /= 2;
ri /= 2;
}
return res;
}
int GetBestPosition(int _N, int C, int R, int *K, int *S, int *E) {
ord.push_back(R);
n = _N;
for(int i = 0 ; i < n - 1; i ++ ){
ord.push_back(K[i]);
}
for(int i = 0 ; i < n; i ++ ){
id[i] = i;
segm[i] = mp(i, i);
}
//build(1, 0, n - 1);
int gl, gr;
int m = n + C;
int el, er;
int tl, tr;
int nid;
for(int i = 0 ; i < LOG; i ++ ){
for(int j = 0 ; j < m ; j ++ ){
par[i][j] = -1;
}
}
vector<int> vse;
for(int i = 0 ; i < n; i ++ ){
vse.push_back(i);
}
for(int qa = 0 ; qa < C; qa ++ ){
vector<int> novij;
segm[n + qa] = mp(vse[S[qa]], vse[E[qa]]);
for(int i = S[qa]; i <= E[qa]; i ++ ){
par[0][id[vse[i]]] = n + qa;
if(i > S[qa])
vse[i] = -1;
else
id[vse[i]] = n + qa;
}
for(auto x : vse)
if(x != -1)
novij.push_back(x);
vse = novij;
}
/*
for(int i = 0 ; i < C; i ++ ){
el = S[i];
er = E[i];
el ++ ;
er ++ ;
tl=tr=-1;
for(int j = el; j <= er; j ++ ){
nid = get(1, 0, n - 1, j);
if(j == el)
tl = nid;
if(j == er)
tr = nid;
par[0][id[nid]] = n + i;
}
reset(1, 0, n - 1, tl + 1, tr);
segm[n + i] = mp(tl, tr);
id[tl] = n + i;
}
*/
for(int lg = 1; lg < LOG; lg ++ ){
for(int i = 0 ; i < m ; i ++ ){
if(par[lg-1][i] != -1){
par[lg][i]=par[lg-1][par[lg-1][i]];
}
}
}
int u, v;
for(int i = 0 ; i < n; i ++ ){
upd(i, ord[i]);
}
int winn = -1;
int maxi = -1;
int cur_cnt;
int node;
int jump;
int chk;
for(int i = 0 ; i < n; i ++ ){
if(i){
upd(i - 1, ord[i]);
upd(i, ord[i - 1]);
swap(ord[i - 1], ord[i]);
}
cur_cnt = 0;
node = i;
while(par[0][node] != -1){
jump = par[0][node];
chk = -1;
for(int j = segm[jump].fi; j <= segm[jump].se; j ++ ){
chk = max(chk, ord[j]);
}
if(chk == ord[i]){
node = jump;
cur_cnt ++ ;
}
else{
break;
}
}
if(cur_cnt > maxi){
maxi = cur_cnt;
winn = i;
}
}
return winn;
}
