#include "books.h"
#include <bits/stdc++.h>
using namespace std;
struct dsu{
vector<int>root;
vector<int>siz;
vector<int>maxima;
vector<int>minima;
dsu(int n){
maxima=vector<int>(n);
iota(maxima.begin(),maxima.end(),0);
minima=vector<int>(n);
iota(minima.begin(),minima.end(),0);
root=vector<int>(n);
iota(root.begin(),root.end(),0);
siz=vector<int>(n,1);
}
bool unite(int x, int y){
x=findRoot(x);
y=findRoot(y);
if(x==y)
return 0;
if(siz[x]<siz[y]){
swap(x,y);
}
siz[x]+=siz[y];
root[y]=x;
maxima[x]=max(maxima[x],maxima[y]);
return 1;
}
int findRoot(int x){
if(x==root[x])
return x;
return root[x]=findRoot(root[x]);
}
};
long long minimum_walk(vector<int> p, int s) {
long long ans = 0;
int n = p.size();
dsu ds(n);
vector<int>interesting;
for(int i = 0;i<n;i++){
ans+=abs(i-p[i]);
ds.unite(i,p[i]);
if(i!=p[i]){
interesting.push_back(i);
}
}
vector<array<int,2>>rangs(n);
for(int i = 0;i<n;i++){
rangs[i][0]=ds.minima[i];
rangs[i][1]=ds.maxima[i];
}
sort(rangs.begin(),rangs.end());
vector<array<int,2>>merged;
for(int i = 0;i<n;i++){
if(rangs[i][0]==rangs[i][1])
continue;
if(merged.size()){
if(rangs[i][0]<merged.back()[1]){
merged.back()[1]=max(merged.back()[1],rangs[i][1]);
}
else{
merged.push_back(rangs[i]);
}
}
else{
merged.push_back(rangs[i]);
}
}
if(merged.size()==0){
return 0;
}
int prev = merged[0][1];
for(int i = 1;i<merged.size();i++){
ans+=2*(merged[i][0]-prev);
prev=merged[i][1];
}
if(s>=merged[0][0]&&s<=merged[merged.size()-1][1]){
int ind = upper_bound(merged.begin(),merged.end(),(array<int,2>){s,1000000000})-merged.begin();
ind--;
if(ind>=0){
if(merged[ind][0]<=s&&s<=merged[ind][1]){
//withing a range, must add something to get into the range.
int upper = upper_bound(interesting.begin(),interesting.end(),s)-interesting.begin();
int lower = s-interesting[upper-1];
upper=interesting[upper]-s;
assert(upper>=0&&lower>=0);
ans+=2*min(lower,upper);
}
}
return ans;
}
ans+=2*min(abs(merged[0][0]-s),abs(merged[merged.size()-1][1]-s));
return ans;
}
