#include "books.h"
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <limits.h>
#define LL long long
#define INF INT_MAX
using namespace std;
int cyc_n;
int cyc_idx[1111111];
int cyc_l[1111111],cyc_r[1111111];
int par[1111111];
int cyc_par[1111111];
int cyc_ldist[1111111],cyc_rdist[1111111];
int cyc_dist[1111111];
int cyc_pos[1111111];
int find_(int x) {
if(par[x]!=x) return par[x]=find_(par[x]);
return x;
}
long long minimum_walk(std::vector<int> P, int s) {
int n=P.size();
LL dist1=0;
int l=n,r=-1;
for(int i=0;i<n;i++){
dist1+=abs(P[i]-i);
if(P[i]!=i) l=min(l,i),r=max(r,i);
}
if(!dist1) return 0;
for(int i=0;i<n;i++){
if(cyc_idx[i]){
cyc_r[cyc_idx[i]]=i;
continue;
}
cyc_idx[i]=++cyc_n;
par[cyc_idx[i]]=cyc_idx[i];
cyc_dist[cyc_idx[i]]=INF;
cyc_l[cyc_idx[i]]=cyc_r[cyc_idx[i]]=i;
int j=P[i];
while(i!=j){
cyc_idx[j]=cyc_idx[i];
j=P[j];
}
}
vector<int> st;
for(int i=0;i<n;i++){
int rt=find_(cyc_idx[i]);
if(cyc_l[rt]==i) st.push_back(rt);
if(!st.empty() && st.back()!=rt){
par[st.back()]=rt;
cyc_l[rt]=min(cyc_l[rt],cyc_l[st.back()]);
cyc_r[rt]=max(cyc_r[rt],cyc_r[st.back()]);
st.pop_back();
}
if(cyc_r[rt]==i) st.pop_back();
}
for(int i=0;i<n;i++){
int rt=find_(cyc_idx[i]);
if(cyc_l[rt]==i){
if(!st.empty()) cyc_par[rt]=st.back();
st.push_back(rt);
}
if(cyc_r[rt]==i) st.pop_back();
}
for(int i=0;i<n;i++){
int rt=find_(cyc_idx[i]);
cyc_pos[rt]=i;
if(cyc_l[rt]==i) cyc_ldist[rt]=i-cyc_pos[cyc_par[rt]];
cyc_pos[cyc_par[rt]]=max(cyc_pos[cyc_par[rt]],i-cyc_ldist[rt]);
cyc_pos[rt]=i;
}
for(int i=n;i--;){
int rt=find_(cyc_idx[i]);
cyc_pos[rt]=i;
if(cyc_r[rt]==i) cyc_rdist[rt]=cyc_pos[cyc_par[rt]]-i;
cyc_pos[cyc_par[rt]]=min(cyc_pos[cyc_par[rt]],i+cyc_rdist[rt]);
cyc_pos[rt]=i;
}
int x=-1;
LL dist2=0;
for(int i=0;i<n;i++){
int rt=find_(cyc_idx[i]);
if(!cyc_par[rt] && cyc_l[rt]==i && cyc_l[rt]!=cyc_r[rt]){
cyc_dist[rt]=0;
if(x!=-1) dist2+=cyc_l[rt]-x;
x=cyc_r[rt];
}
else cyc_dist[rt]=min(cyc_ldist[rt],cyc_rdist[rt]);
}
LL dist3=0;
int rt=find_(cyc_idx[s]);
if(cyc_par[rt]){
while(cyc_par[rt]){
dist3+=cyc_dist[rt];
rt=cyc_par[rt];
}
}
else if(s<l) dist3=l-s;
else if(r<s) dist3=s-r;
return dist1+((dist2+dist3)<<1);
}
