#include <iostream>
#include <algorithm>
#include "books.h"
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> pll;
int N,S;
int UFp[1000006],UFh[1000006];
ll P[1000006];
int C[1000006];
ll ans;
int c;
ll ult1,ult2=-1;
vector<pll> V;
int UFfind(int k){
int a;
for(a=k;a!=UFp[a];a=UFp[a]);
UFp[k]=a;
return a;
}
void UFunion(int x, int y){
x=UFfind(x);
y=UFfind(y);
if(UFh[x]<UFh[y])
swap(x,y);
UFp[y]=UFp[x];
UFh[x]=max(UFh[x],UFh[y]+1);
}
long long minimum_walk(std::vector<int> q, int s) {
N=q.size();
S=s;
for(int i=0;i<N;i++){
P[i]=q[i];
ans+=abs(P[i]-(ll)i);
}
for(int i=0;i<N;i++){
UFp[i]=i;
UFh[i]=1;
}
fill(C,C+N,-1);
for(int i=0;i<N;i++)
if(C[i]==-1 and (i==0 or P[i]!=i)){
int a=P[i];
C[i]=c;
while(a!=i){
C[a]=c;
a=P[a];
}
c++;
}
for(ll i=0;i<N;i++)
for(ll j=i-1;j>=0;j--)
if(C[i]!=C[j] and P[i]!=i and (P[j]!=j or j==0))
V.push_back({i-j,i});
sort(V.begin(),V.end());
int p=0;
for(int g=0;g<c-1;g++){
while(UFfind(V[p].second)==UFfind(V[p].second-V[p].first))
p++;
ans+=V[p].first*2;
UFunion(V[p].second,V[p].second-V[p].first);
}
return ans;
}
/*
for(int i=0;i<N;i++)
cout<<P[i]<<" "<<C[i]<<endl;
for(auto p:V)
cout<<p.first<<" "<<p.second<<" "<<p.second-p.first<<endl;
*/
