#include "books.h"
#include <bits/stdc++.h>
#define f first
#define s second
#define vec vector
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define m_p make_pair
#define sz(x) (int)(x).size()
#define pw(x) (1LL<<(x))
//#define pragma optimize("unroll-loops")
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
template <class T> bool umin(T &a,const T &b){return (a>b?a=b,1:0);}
template <class T> bool umax(T &a,const T &b){return (a<b?a=b,1:0);}
const int N=1e6+3;
struct dsu{
int p[N],sz[N];
void make(int v){
p[v]=v;
sz[v]=1;
}
void init(){
for(int i=0;i<N;i++)
make(i);
}
int get(int v){
return p[v]=(p[v]==v?v:get(p[v]));
}
bool mg(int a,int b){
a=get(a),b=get(b);
if(a==b) return 0;
if(sz[a]>sz[b]) swap(a,b);
p[a]=b;sz[b]+=sz[a];
return 1;
}
}ds;
long long minimum_walk(std::vector<int> p, int s) {
ds.init();
int n=sz(p);
vec<int>used(n,0);
vec<int>rgt(n,0);
ll ans=0;
vec<pii> arr;
for(int i=0;i<n;i++){
if(used[i]) continue;
int j=i;
vec<int>vc;
while(!used[j]){
used[j]=1;
vc.pb(j);
ans+=abs(p[j]-j);
j=p[j];
}
int mx=*max_element(all(vc));
for(auto &z : vc){
rgt[z]=mx;
}
if(sz(vc)==1) {cerr<<"J "<<i<<endl;continue;}
arr.pb({i,mx});
// cout<<"HEY "<<endl;
//// for(auto &z : vc)
// cout<<z<<' ';
// cout<<endl;
}
vec<pii> narr;
for(auto &z : arr){
if(!sz(narr) || narr.back().s<z.f) narr.pb(z);
else umax(narr.back().s,z.s);
}
swap(arr,narr);
vec<int> incomp(n,-1);
int j=0;
for(auto &z : arr){
for(int i=z.f;i<=z.s;i++){
if(p[i]!=i) incomp[i]=j;
}
j++;
}
vec<array<int,3>> e;
for(int i=0;i<n;i++){
if(incomp[i]!=-1){
e.pb({2*abs(s-i),incomp[i],n});
}
}
ds.init();
// for(int i=0;i<sz(arr);i++){
// e.pb({2*min(abs(s-arr[i].f),abs(s-arr[i].s)),i,n});
//// cout<<"I "<<i<<' '<<arr[i].f<<' '<<arr[i].s<<endl;
// }
for(int i=1;i<sz(arr);i++){
e.pb({2*abs(arr[i].f-arr[i-1].s),i,i-1});
}
sort(all(e));
for(auto &z : e){
// cout<<"Z "<<z[0]<<' '<<z[1]<<' '<<z[2];
if(ds.mg(z[1],z[2]))
ans+=z[0];
}
return ans;
}
