#include "books.h"
#include <bits/stdc++.h>
using namespace std;
int p,h,POS[1000000],tree[1<<21];
long long d;
vector<int>P;
void movel(int x){
for(int i=p;i>=x;i--){
if(h>P[i]){
swap(h,P[i]);
}
}
d+=p-x;
p=x;
}
void mover(int x){
for(int i=p;i<=x;i++){
if(h<P[i]){
swap(h,P[i]);
}
}
d+=x-p;
p=x;
}
void update(int x){
x+=1<<20;
while(x){
tree[x]++;
x/=2;
}
}
int calc(int l,int r){
l+=1<<20;
r+=1<<20;
int a=0;
while(l<r){
if(l&1)a+=tree[l];
if(~r&1)a+=tree[r];
l=(l+1)/2;
r=(r-1)/2;
}
if(l==r)a+=tree[l];
return a;
}
long long minimum_walk(vector<int>ppp,int S){
P=ppp;
assert(S==0);
int N=P.size();
p=0;
d=0;
h=-1;
for(int a=N-1;a>=0;a--){
if(P[a]!=a){
movel(a);
for(int i=0;i<N;i++){
POS[P[i]]=i;
}
for(int i=a;i<N;i++){
update(POS[i]);
}
for(int i=a-1;i>0;i--){
p--;
d++;
d+=1+max(0,i-POS[i])*2;
update(POS[i]);
}
}
}
return d+p;
}
