#include "books.h"
#include<bits/stdc++.h>
#define ll int
#define pb push_back
#define mp make_pair
#define ld long double
#define F first
#define S second
#define pii pair<ll,ll>
using namespace :: std;
const ll maxn=1e6+500;
const ll inf=1e9+900;
const ll logg=20;
vector<ll> p;
bool vis[maxn];
ll d[maxn];
ll last=-1,fir,N;
ll cnt=0;
ll mxx[maxn];
ll mnn[maxn];
ll l[maxn];
ll r[maxn];
map<pii,ll> ml;
ll ras[maxn];
vector<pii> ger[maxn];
ll fas[maxn];
void addYal(ll a,ll b,ll w){
ger[a].pb(mp(b,w));
}
void bfs(ll a){
fill(fas,fas+maxn,inf);
deque<ll> qu;
qu.pb(a);
fas[a]=0;
while(qu.size()){
ll v=qu.back();
qu.pop_back();
for(auto e:ger[v]){
if(fas[e.F]==inf){
fas[e.F]=fas[v]+e.S;
if(e.S==0){
qu.pb(e.F);
}else{
qu.push_front(e.F);
}
}
}
}
}
void dfs(ll a){
if(vis[a])return;
vis[a]=2;
d[a]=cnt;
dfs(p[a]);
}
long long minimum_walk(vector<int> P, int s){
p=P;
ll n=p.size();
N=n;
long long ans=0;
for(ll i=0;i<n;i++){
if(!vis[i]){
dfs(i);
cnt++;
}
if(p[i]!=i)last=i;
ans+=abs(i-p[i]);
}
for(ll i=n-1;i>=0;i--){
if(p[i]!=i){
fir=i;
}
}
if(last==-1)return 0;
fill(mnn,mnn+maxn,inf);
fill(mxx,mxx+maxn,0);
for(ll i=0;i<n;i++){
mnn[d[i]]=min(mnn[d[i]],i);
mxx[d[i]]=max(mxx[d[i]],i);
}
if(s<=fir){
ll t=s;
for(ll i=s;i<=last;i++){
if(t<i){
ans+=2;
t=max(t,i);
}
t=max(t,mxx[d[i]]);
}
return ans;
}
if(s>=last){
ll t=s;
for(ll i=s;i>=fir;i--){
if(i<t){
ans+=2;
t=min(t,i);
}
t=min(t,mnn[d[i]]);
}
return ans;
}
ll minn,maxx;
minn=fir;
maxx=fir;
for(ll i=fir;i<s;i++){
minn=min(minn,mnn[d[i]]);
maxx=max(maxx,mxx[d[i]]);
if(maxx==i){
ans+=2;
fir=i+1;
}
}
minn=last;
maxx=last;
for(ll i=last;i>s;i--){
minn=min(minn,mnn[d[i]]);
maxx=max(maxx,mxx[d[i]]);
if(minn==i){
ans+=2;
last=i-1;
}
}
minn=s;
maxx=s;
for(ll i=s;i<n;i++){
minn=min(minn,mnn[d[i]]);
maxx=max(maxx,mxx[d[i]]);
l[i]=minn;
r[i]=maxx;
}
minn=s;
maxx=s;
for(ll i=s;i>=0;i--){
minn=min(minn,mnn[d[i]]);
maxx=max(maxx,mxx[d[i]]);
l[i]=minn;
r[i]=maxx;
}
for(ll i=0;i<n;i++){
l[i]=max(l[i],fir);
r[i]=min(r[i],last);
}
cnt=0;
for(ll i=fir;i<=last;i++){
if(ml.count(mp(l[i],r[i]))==0){
ml[mp(l[i],r[i])]=cnt++;
}
ras[i]=ml[mp(l[i],r[i])];
}
ll start=ras[s];
for(ll i=fir;i<=last;i++){
ll v=ml[mp(l[i],r[i])];
addYal(v,ras[l[i]],0);
addYal(v,ras[r[i]],0);
if(i!=fir){
addYal(v,ras[i-1],1);
}
if(i!=last){
addYal(v,ras[i+1],1);
}
}
bfs(start);
ll res=min(fas[ras[fir]],fas[ras[last]]);
return ans+res*2;
}
