#include "books.h"
#include<bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef long double ld;
template <typename T> bool chkmin(T &x,T y){return x>y?x=y,1:0;}
template <typename T> bool chkmax(T &x,T y){return x<y?x=y,1:0;}
ll readint(){
ll x=0,f=1; char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
bool was[1000005];
int n,sl[1000005],sr[1000005],rt[1000005];
namespace rmq{
int mina[1000005][22],maxa[1000005][22],logs[1000005];
void build(){
for(int i=2;i<=n;i++) logs[i]=logs[i>>1]+1;
for(int i=0;i<n;i++){
mina[i][0]=sl[rt[i]];
maxa[i][0]=sr[rt[i]];
}
for(int j=1;j<22;j++){
for(int i=0;i+(1<<j)<=n;i++){
mina[i][j]=min(mina[i][j-1],mina[i+(1<<(j-1))][j-1]);
maxa[i][j]=max(maxa[i][j-1],maxa[i+(1<<(j-1))][j-1]);
}
}
}
int qmin(int l,int r){
int k=logs[r-l+1];
return min(mina[l][k],mina[r-(1<<k)+1][k]);
}
int qmax(int l,int r){
int k=logs[r-l+1];
return max(maxa[l][k],maxa[r-(1<<k)+1][k]);
}
};
void work(int&l,int&r){
while(true){
int fl=rmq::qmin(l,r);
int fr=rmq::qmax(l,r);
if(fl==l&&fr==r) break;
l=fl; r=fr;
}
}
ll minimum_walk(vector<int> p,int s){
n=(int)p.size();
ll ans=0;
for(int i=0;i<n;i++) ans+=abs(p[i]-i);
for(int i=0;i<n;i++){
if(was[i]) continue;
sl[i]=i; sr[i]=i;
rt[i]=i;
int x=i;
while(!was[x]){
chkmin(sl[i],x);
chkmax(sr[i],x);
rt[x]=i;
was[x]=true;
x=p[x];
}
}
rmq::build();
int L=s,R=s;
for(int i=0;i<n;i++){
if(p[i]==i) continue;
chkmin(L,i); chkmax(R,i);
}
int cl=s,cr=s;
while(cl>L||cr<R){
work(cl,cr);
int nl=cl,nr=cr;
int pl=cl,pr=cr;
ll a=0;
bool lt=false;
while(pl>L&&pr==cr){
a+=2;
pl--;
work(pl,pr);
}
chkmin(nl,pl);
chkmax(nr,pr);
if(pr>cr) lt=true;
pl=cl; pr=cr;
ll b=0;
bool rt=false;
while(pl==cl&&pr<R){
b+=2;
pr++;
work(pl,pr);
}
chkmin(nl,pl);
chkmax(nr,pr);
if(pl<cl) rt=true;
if(lt&&rt) ans+=min(a,b);
else ans+=a+b;
cl=nl; cr=nr;
}
return ans;
}
