#include "books.h"
#include <cstdio>
#include <vector>
#include <cassert>
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e6+6;
int id[N],lp[N],rp[N];
typedef vector<int> vi;
void extend(int &ll,int &rr,vi &c,vi &l,vi &r)
{
int lp=min(l[c[ll]],l[c[rr]]),rp=max(r[c[ll]],r[c[rr]]);
while(ll>lp||rr<rp)
{
// cout<<lp<<'*'<<rp<<' '<<ll<<' '<<rr<<endl;
if(ll>lp)
{
--ll;
lp=min(lp,l[c[ll]]);
rp=max(rp,r[c[ll]]);
}else{
++rr;
lp=min(lp,l[c[rr]]);
rp=max(rp,r[c[rr]]);
}
}
}
LL go(int l,int r,int tl,int tr,vi &c,vi &lc,vi &rc)
{
int ans=0;
int nl,nr;
// cout<<l<<' '<<r<<' '<<tl<<' '<<tr<<'\n';
while(l>tl||r<tr)
{
extend(l,r,c,lc,rc);
// cout<<l<<' '<<r<<endl;
int ll=l,rl=l,ansl=0,nextl=0;
while(1)
{
if(ll<=tl)
{
break;
}
ll--;ansl+=2;
extend(ll,rl,c,lc,rc);
if(rl>r)
{
nextl=1;
break;
}
}
// cout<<ll<<' '<<rl<<" l\n";
int lr=r,rr=r,ansr=0,nextr=0;
while(1)
{
if(rr>=tr)
{
break;
}
rr++;ansr+=2;
extend(lr,rr,c,lc,rc);
if(lr<l)
{
nextr=1;
break;
}
}
// cout<<lr<<' '<<rr<<" r\n";
assert(!(nextl^nextr));
if(nextl&&nextr)
{
ans+=min(ansl,ansr);
}else{
ans+=ansl+ansr;
}
l=min(ll,lr);
r=max(rl,rr);
}
return ans;
}
long long minimum_walk(std::vector<int> p, int s) {
//essential edges
LL ans=0;
int n=p.size();
vector<int>c(n),l(n),r(n);
int tot=0,L=s,R=s;
for(int i=0;i<n;i++)
{
ans+=abs(i-p[i]);
if(c[i]==0)
{
++tot;
l[tot]=i;r[tot]=i;c[i]=tot;
for(int x=p[i];x!=i;x=p[x])
{
c[x]=tot;r[tot]=max(r[tot],x);
}
if(i!=p[i])
{
L=min(L,l[tot]);
R=max(R,r[tot]);
}
}
}
// cout<<ans<<'\n';
return ans+go(s,s,L,R,c,l,r);
}
