#include<bits/stdc++.h>
using namespace std;
#define _ int v, int tl, int tr, int l, int r
#define tm (tl+tr >> 1)
#define sol v+v,tl,tm,l,r
#define sag v+v+1,tm+1,tr,l,r
#define mp make_pair
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef pair < ll , ll > pp;
const int mod = 1e9 + 7;
const int N = 1e6 + 6;
set < int > W[N];
int H[N],T[N],n,i,j,l,r,t,a,b,mn,mx,u,h;
int smn[N<<2],smx[N<<2];
ll x;
void up(int p) { // set value at position p
for (smn[p += n] = a, smx[p] = b; p > 1; p >>= 1){
smn[p>>1] = min(smn[p] , smn[p^1]);
smx[p>>1] = max(smx[p] , smx[p^1]);
}
}
void qry(int l, int r) { // sum on interval [l, r)
r++;
for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
if (l&1) { mn = min(mn , smn[l]); mx = max(mx , smx[l]); l++; }
if (r&1) { r--; mn = min(mn , smn[r]); mx = max(mx , smx[r]); }
}
}
ll minimum_walk(vector < int > p, int s){
x = 0;
n = p.size();
// if(n > 1000) return 0;
memset(smn , 22 , sizeof smn);
for(i=0;i<n;i++){
x += abs(p[i] - i);
if(H[i]) continue;
r = i;
for(j=i; !H[j] ; j = p[j]){
H[j] = 1;
r = max(r , j);
}
for(j=i; !T[j] ; j = p[j]){
T[j] = 1;
a = i; b = r;
up(j);
}
}
for(i=0;i<n && p[i] == i; i++);
for(j=n-1;j>=0 && p[j] == j; j--);
queue < pair < int , pp > > Q[2];
Q[h=0].push(mp(0,mp(s,s)));
for(;;){
if(Q[h].size() == 0) h = !h;
l = Q[h].front().nd.st;
r = Q[h].front().nd.nd;
u = Q[h].front().st;
Q[h].pop();
if(W[l].find(r) != W[l].end()) continue;
// cout << l << " " << r << " " << -u << " aa\n";
if(l <= i && r >= j) return x + -u-u;
W[l].insert(r);
mn = n; mx = 0;
qry(l,r);
Q[h].push(mp(u,mp(mn,mx)));
if(l) Q[!h].push(mp(u-1,mp(l-1,r)));
if(r < n-1) Q[!h].push(mp(u-1,mp(l,r+1)));
}
}
/*
int main(){
cout << minimum_walk({1,0,2,3} , 2);
}*/
