#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;
vector<ll> p;
bool vis[maxn];
ll d[maxn];
ll last=-1,fir,N;
ll cnt=0;
ll mxx[maxn];
ll mnn[maxn];
const ll maxm=1050;
bool visdp[maxm][maxm];
ll dpp[maxm][maxm];
ll findmnn[maxm][maxm];
ll findmxx[maxm][maxm];
ll findDp(ll l,ll r){
l=max(l,0);
r=min(r,N-1);
if(l<=fir && last<=r)return 0;
if(visdp[l][r])return dpp[l][r];
visdp[l][r]=1;
dpp[l][r]=inf;
if(findmnn[l][r]<l){
dpp[l][r]=findDp(findmnn[l][r],r);
}else if(findmxx[l][r]>r){
dpp[l][r]=findDp(l,findmxx[l][r]);
}else{
dpp[l][r]=min(findDp(l,r+1)+2,findDp(l-1,r)+2);
}
return dpp[l][r];
}
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;
}
if(n<=1000){
for(ll t=1;t<=n;t++){
for(ll l=0;l+t-1<n;l++){
ll r=l+t-1;
if(t==1){
findmnn[l][r]=mnn[d[l]];
findmxx[l][r]=mxx[d[l]];
}else{
findmnn[l][r]=min(findmnn[l][r-1],mnn[d[r]]);
findmxx[l][r]=max(findmxx[l][r-1],mxx[d[r]]);
}
}
}
return findDp(mnn[d[s]],mxx[d[s]])+ans;
}
return ans;
}
