#include "books.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef pair<int,int> pi;
typedef vector<pi> pii;
typedef tuple<int,int,int> ti;
typedef vector<ll> li;
typedef vector<li> lii;
#define REP(i,a,b) for(int i=a;i<b;i++)
#define F first
#define S second
#define PB push_back
#define LSOne(s) ((s)&(-s))
#define all(x) (x).begin(),(x).end()
ll INF=1000000000000000010;
int inf=1e9+10;
ll M=1e9+7;
vi a,vis,arr;
ll dp[1000][1000];
map<pi,pi> par;
map<pi,int> mn,mx,sz;
pi parent(pi x){
if(par[x]==x)return x;
return par[x]=parent(par[x]);
}
void merge(pi x,pi y){
if(x.F>y.F)swap(x,y);
if(x.S<y.F)return;
x=parent(x);
y=parent(y);
if(x==y)return;
if(sz[x]<sz[y])swap(x,y);
sz[x]+=sz[y];
mn[x]=min(mn[x],mn[y]);
mx[x]=max(mx[x],mx[y]);
par[y]=x;
}
void dfs(int x){
arr.PB(x);
vis[x]=1;
if(vis[a[x]]==0)dfs(a[x]);
}
long long minimum_walk(std::vector<int> p, int s) {
a=p;
while(a.size()&&a[a.back()]==a.back())a.pop_back();
if(a.size()==0)return 0;
int n=a.size();
vis.resize(n,0);
int pos=0;
while(pos<n&&a[pos]==pos)pos++;
ll ans=0;
if(s>=n){
ans=(s-n+1)*2LL;
s=n-1;
}
vector<pi> c(n,{-1,-1}),d;
REP(i,pos,n)if(!vis[i]&&i!=a[i]){
arr.clear();
dfs(i);
sort(all(arr));
for(auto u:arr)ans+=(ll)abs(u-a[u]);
for(auto u:arr)c[u]={arr[0],arr.back()};
par[{arr[0],arr.back()}]={arr[0],arr.back()};
sz[{arr[0],arr.back()}]=1;
mn[{arr[0],arr.back()}]=arr[0];
mx[{arr[0],arr.back()}]=arr.back();
d.PB({arr[0],arr.back()});
}
sort(all(d));
REP(i,0,d.size())REP(j,i+1,d.size())merge(d[i],d[j]);
REP(i,0,n)if(c[i].F!=-1)c[i]={mn[parent(c[i])],mx[parent(c[i])]};
REP(i,0,1000)REP(j,0,1000)dp[i][j]=INF;
dp[s][s]=0;
for(int i=n-1;i>=0;i--)REP(j,i,n)if(dp[i][j]!=INF){
if(i!=0)dp[i-1][j]=min(dp[i-1][j],dp[i][j]+2);
if(j!=n-1)dp[i][j+1]=min(dp[i][j+1],dp[i][j]+2);
if(c[i].F!=-1)dp[min(i,c[i].F)][max(j,c[i].S)]=min(dp[min(i,c[i].F)][max(j,c[i].S)],dp[i][j]);
if(c[j].F!=-1)dp[min(i,c[j].F)][max(j,c[j].S)]=min(dp[min(i,c[j].F)][max(j,c[j].S)],dp[i][j]);
}
return dp[min(pos,s)][n-1]+ans;
}
