#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;
}
};
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);
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));
}
return ans+dp[0][n-1]*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;
*/
}
