#include "books.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e6;
struct DSU{
ll p[N];
ll sz;
void init(ll n){
sz=n;
for(ll i=0; i<n; i++){
p[i]=i;
}
}
ll find(ll u){
if(p[u]==u) return u;
else return p[u]=find(p[u]);
}
void merge(ll u, ll v){
u=find(u);
v=find(v);
if(u==v) return;
sz--;
p[u]=v;
}
};
long long minimum_walk(vector<int> a, int s){
ll n=a.size();
DSU dsu;
dsu.init(n);
ll ans=0;
for(ll i=0; i<n; i++){
dsu.merge(i,a[i]);
ans+=abs(i-a[i]);
}
vector<pair<ll,pair<ll,ll>>> x;
ll prev=0;
for(ll i=1; i<n; i++){
if(a[i]==i) continue;
if(dsu.find(prev)!=dsu.find(i)){
x.push_back({i-prev,{i,prev}});
}
prev=i;
}
sort(x.begin(),x.end());
for(auto i:x){
if(dsu.find(i.second.first)!=dsu.find(i.second.second)){
dsu.merge(i.second.first,i.second.second);
ans+=2*i.first;
}
}
return ans;
}
