#include "books.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> ii;
#define maxn 1000005
int n,cl[maxn],cr[maxn],c[maxn];
void extend(int &l,int &r){
//printf("extend: %d %d\n",l,r);
int farl=min(cl[c[l]],cl[c[r]]);
int farr=max(cr[c[l]],cr[c[r]]);
while(true){
if(farl<l){
--l;
farl=min(farl,cl[c[l]]);
farr=max(farr,cr[c[l]]);
}
else if(r<farr){
++r;
farl=min(farl,cl[c[r]]);
farr=max(farr,cr[c[r]]);
}
else break;
}
//printf("res: %d %d\n",l,r);
}
ll minimum_walk(vector<int> p,int s){
n=p.size();
int lbound=s,rbound=s;
ll ans=0;int cnt=1;
for(int i=0;i<n;++i){
if(c[i]!=0)continue;
int x=i;
cl[cnt]=i;
while(true){
c[x]=cnt;
cr[cnt]=max(cr[cnt],x);
ans+=abs(x-p[x]);
x=p[x];
if(x==i)break;
}
if(i!=p[i]){
lbound=min(lbound,cl[cnt]);
rbound=max(rbound,cr[cnt]);
}
++cnt;
}
int l=s,r=s;
while(l!=lbound||r!=rbound){
//printf("%d %d\n",l,r);
extend(l,r);
bool can=false;
int newl=n,newr=0;
int tmpl=l,tmpr=r;
int lcost=0;
while(true){
if(tmpl<=lbound)break;//done
--tmpl;lcost+=2;
extend(tmpl,tmpr);
if(tmpr>r){
can=true;
break;
}
}
newl=min(newl,tmpl);
newr=max(newr,tmpr);
tmpl=l,tmpr=r;
int rcost=0;
while(true){
if(tmpr>=rbound)break;//done
++tmpr;rcost+=2;
extend(tmpl,tmpr);
if(tmpl<l){
can=true;
break;
}
}
newl=min(newl,tmpl);
newr=max(newr,tmpr);
if(can)ans+=min(lcost,rcost);
else ans+=lcost+rcost;
l=tmpl,r=tmpr;
}
return ans;
}
