#include "books.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const ll INF=1e9+7;
const int LIM=1e3+7;
ll F[LIM], mi[LIM], ma[LIM], dp[LIM][LIM], dpma[LIM][LIM], dpmi[LIM][LIM], l, r;
ll fnd(ll x) {
if(F[x]==x) return x;
return F[x]=fnd(F[x]);
}
void uni(int a, int b) {
if(fnd(a)==fnd(b)) return;
ma[fnd(a)]=max(ma[fnd(a)], ma[fnd(b)]);
mi[fnd(a)]=min(mi[fnd(a)], mi[fnd(b)]);
F[fnd(b)]=fnd(a);
}
ll minimum_walk(vector<int>p, int s) {
ll n=p.size();
rep(i, n) F[i]=ma[i]=mi[i]=i;
rep(i, n) uni(i, p[i]);
l=0; r=n-1;
while(l<s && p[l]==l) ++l;
while(r>s && p[r]==r) --r;
rep(i, n) {
dpma[i][i]=ma[fnd(i)];
dpmi[i][i]=mi[fnd(i)];
for(int j=i+1; j<n; ++j) {
dpma[i][j]=max(dpma[i][j-1], ma[fnd(j)]);
dpmi[i][j]=min(dpmi[i][j-1], mi[fnd(j)]);
}
}
ll ans=0;
rep(i, n) ans+=abs(p[i]-i);
for(ll d=r-l; d>0; --d) {
for(ll a=l; a+d-1<=r; ++a) {
ll b=a+d-1;
if(dpmi[a][b]<a) dp[a][b]=dp[a-1][b];
else if(dpma[a][b]>b) dp[a][b]=dp[a][b+1];
else if(a==l) dp[a][b]=dp[a][b+1]+2;
else if(b==r) dp[a][b]=dp[a-1][b]+2;
else dp[a][b]=min(dp[a-1][b], dp[a][b+1])+2;
}
}
return ans+dp[s][s];
}
