#include "books.h"
#include<bits/stdc++.h>
using namespace std;
const int N=(1<<20);
int tab[N+N];
const int INF=1e9;
void ust(int l, int r, int m){
r++;
for(l+=N, r+=N; l<r; l>>=1, r>>=1){
if(l&1){
tab[l]=min(tab[l], m);
l++;
}
if(r&1){
--r;
tab[r]=min(tab[r], m);
}
}
}
int quer(int id){
int ans=INF;
for(id+=N; id>0; id>>=1){
ans=min(ans, tab[id]);
}
return ans;
}
long long minimum_walk(std::vector<int> p, int s) {
int n=p.size();
/*s=n-s-1;
for(int i=0; i<n; i++){
p[i]=n-p[i]-1;
}
reverse(p.begin(), p.end());*/
long long ans=0;
for(int i=0; i<n; i++){
ans+=abs(i-p[i]);
}
vector<int> V(n), col(n);
int sum=0;
for(int i=0; i<n; i++){
sum-=V[i];
sum-=V[p[i]];
V[i]^=1;
V[p[i]]^=1;
sum+=V[i];
sum+=V[p[i]];
if(sum)col[i]=1;
}
bool czy=0;
for(int i=0; i<s; i++){
if(col[i])czy=1;
if(czy && !col[i])ans+=2;
}
czy=0;
for(int i=n-1; i>=s; i--){
if(col[i])czy=1;
if(czy && !col[i])ans+=2;
}
for(int i=1; i<N+N; i++){
tab[i]=INF;
}
ust(s, s, 0);
int l=s, r=s;
while(l>=0 || r<n){
if(l<0 || quer(l)>quer(r)){
if(r<n-1)ust(r+1, r+1, quer(r)+1);
ust(min(r, p[r]), max(r, p[r]), quer(r));
r++;
}
else{
if(l)ust(l-1, l-1, quer(l)+1);
ust(min(l, p[l]), max(l, p[l]), quer(l));
l--;
}
}
int k=0;
for(int i=0; i<n; i++){
if((s-i)*(long long)(s-p[i])<0){
k=max(k, quer(i));
}
}
ans+=2*k;
return ans;
}
