#include "books.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e6;
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=s;
// for(ll i=0; 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;
// }
// }
ll l=0;
while(l<s && a[l]==l) l++;
ll r=n-1;
while(r>s && a[r]==r) r--;
ll x[n]={};
for(ll i=0; i<n; i++){
if(dsu.p[i]!=i) continue;
x[dsu.x_min[i]]++;
x[dsu.x_max[i]]--;
}
ll y=0;
for(ll i=l; i<r; i++){
y+=x[i];
if(y==0) ans+=2;
}
return ans;
}
