#include "books.h"
#include<bits/stdc++.h>
#define int long long
#define vi vector<int>
#define vb vector<bool>
#define pii pair<int,int>
#define vpii vector<pair<int,int>>
#define vvi vector<vi>
#define mp make_pair
#define pb push_back
#define F first
#define S second
#define f0r(i,n) for(int i = 0; i<n; i++)
#define FOR(i, k, n) for(int i = k; i<n; i++)
#define dout(x) cout<<x<<' '<<#x<<endl;
#define dout2(x,y) cout<<x<<' '<<#x<<' '<<y<<' '<<#y<<endl;
#define vout(x) for(auto u : x)cout<<u<<' '; cout<<endl;
using namespace std;
inline pii mrg(pii a, pii b){return mp(min(a.F,b.F),max(a.S,b.S));}
struct segtree{
int n; vpii tree;
segtree(vpii &v){
n=v.size(); tree.resize(n*2+5); for(int i = n; i < 2 * n; i++)tree[i]=v[i-n]; for(int i = n-1; i >= 1; i--)tree[i]=mrg(tree[i*2],tree[i*2+1]);
}
pii quer(int l, int r){
pii ret = mp(1e9,-1e9); l+=n;r+=n; while(l<=r){
if(l%2)ret=mrg(ret,tree[l++]); if(r%2==0)ret=mrg(ret,tree[r--]); l/=2;r/=2;
} return ret;
}
};
struct seg{
int n; vi mn, mx;
seg(vi &a, vi &b){
n=a.size(); mn.resize(4*n+5); mx.resize(4*n+5); buildmn(1,0,n-1,a); buildmx(1,0,n-1,b);
}
void pull(int v){
mn[v]=min(mn[v*2],mn[v*2+1]); mx[v]=max(mx[v*2],mx[v*2+1]);
}
void buildmn(int v, int l, int r, vi &a){
if(l==r){mn[v]=a[l]; return;} int mid = l + r >> 1; buildmn(v*2,l,mid,a); buildmn(v*2+1,mid+1,r,a); pull(v);
}
void buildmx(int v, int l, int r, vi &a){
if(l==r){mx[v]=a[l]; return;} int mid = l + r >> 1; buildmx(v*2,l,mid,a); buildmx(v*2+1,mid+1,r,a); pull(v);
}
int last_larger(int v, int tl, int tr, int l, int r, int x){
if(mx[v] < x)return -1; if(tl > r || tr < l)return -1; if(tl==tr)return tl;
int tm = tl + tr >> 1; int lef = last_larger(v*2+1,tm+1,tr,l,r,x); if(lef!=-1)return lef;
return last_larger(v*2,tl,tm,l,r,x);
}
int first_less(int v, int tl, int tr, int l, int r, int x){
if(mn[v] > x)return -1; if(tl > r || tr < l)return -1; if(tl==tr)return tl;
int tm = tl + tr >> 1; int lef = first_less(v*2,tl,tm,l,r,x); if(lef!=-1)return lef;
return first_less(v*2+1,tm+1,tr,l,r,x);
}
};
long long minimum_walk(std::vector<signed> p, signed s) {
int n = p.size(), ans = 0; f0r(i,n)ans+=abs(p[i]-i); vector<bool>vis(n); vector<pair<int,int>>r(n); f0r(i,n)if(!vis[i]){
int cur = i; vi v; int mn = 1e9, mx = -1e9; while(!vis[cur]){vis[cur] = 1; v.pb(cur); mn=min(mn,cur),mx=max(mx,cur); cur = p[cur];}
for(auto u : v)r[u]=mp(mn,mx);
} segtree S = segtree(r); //for(auto u : r)cout<<u.first<<' '<<u.second<<'\n'; S.quer(0,0);
int a = 1e9, b = -1e9; f0r(i,n)if(p[i]!=i)a=min(a,i),b=max(b,i); if(a==1e9)return ans;
vi ls, rs; f0r(i,n)ls.pb(r[i].F),rs.pb(r[i].S); seg T = seg(ls,rs); int L = s, R = s;
vi dif(n); f0r(i,n){int a = i, b = p[i]; if(a>b)swap(a,b); dif[a]++; dif[b]--;}
while(1){
while(1){
auto [l_, r_] = S.quer(L,R); if(l_==L&&r_==R)break; L=l_, R=r_;
}
int cl = T.last_larger(1,0,n-1,0,L-1,s); if(cl==-1){
if(L>a){
L--; ans+=2; int cur = 0; while(L>a){
cur -= dif[L]; if(cur==0)ans+=2; L--;
}
}
if(R<b){
R++; ans+=2; int cur = 0; while(R<b){
cur += dif[R]; if(cur==0)ans+=2; R++;
}
}
break;
}
int cur = 0, lcost = 1; for(int i = L-1; i >= cl + 1; i--){
cur -= dif[i]; if(cur==0)lcost++;
}
int cr = T.first_less(1,0,n-1,R+1,n-1,s); cur = 0; int rcost = 1; for(int i = R+1; i<cr; i++){
cur += dif[i]; if(cur==0)rcost++;
} //dout2(L,R); dout2(cl,cr);
ans += min(lcost, rcost) * 2; L = cl, R = cr;
} return ans;
/*
vvi dp(n, vi(n,1e9)); dp[s][s]=0; deque<pii>q; q.push_front(mp(s,s)); while(!q.empty()){
int x = q.front().F, y = q.front().S; q.pop_front();
auto [x_, y_] = S.quer(x,y); if(dp[x_][y_]==1e9){
dp[x_][y_] = dp[x][y]; q.push_front(mp(x_,y_));
}
if(y+1 < n && dp[x][y+1]==1e9)dp[x][y+1]=dp[x][y]+1,q.pb(mp(x,y+1));
if(x-1 >= 0 && dp[x-1][y]==1e9)dp[x-1][y]=dp[x][y]+1,q.pb(mp(x-1,y));
} int mn = 1e9; f0r(i,n)FOR(j,i,n)if(i<=a&&j>=b)mn=min(mn,dp[i][j]);
return ans+mn*2;
*/
/*
vi dif(n); f0r(i,n){int a = i, b = p[i]; if(a>b)swap(a,b); dif[a]++; dif[b]--;}
int cur = 0; vi w(n-1); int lst = -1; f0r(i,n-1){cur+=dif[i]; if(cur)w[i]=1,lst=i;}
for(int i = lst; i >= 0; i--)if(w[i]==0)ans+=2; return ans;
*/
}
