#include "books.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e5;
struct DSU{
ll p[N], x_min[N], x_max[N];
ll sz;
void init(ll n){
sz=n;
for(ll i=0; i<n; i++){
p[i]=i;
x_min[i]=i;
x_max[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--;
x_max[v]=max(x_max[v],x_max[u]);
x_min[v]=min(x_min[v],x_min[u]);
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 && i!=s) continue;
if(dsu.find(prev)!=dsu.find(i)){
x.push_back({i-prev,{i,prev}});
}
prev=i;
}
for(ll i=0; i<n; i++){
if(dsu.p[i]!=i) continue;
for(ll j=i+1; j<n; j++){
if(dsu.p[j]!=j) continue;
if(max(dsu.x_min[i],dsu.x_min[j])<min(dsu.x_max[i],dsu.x_max[j])) x.push_back({0,{i,j}});
}
}
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;
}
