#include "books.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> p;
pair<int,int> dp[1005][1005];
bool calc[1005][1005];
int mn[1005][1005],mx[1005][1005],dist[1005][1005];
pair<int,int> solve(int l,int r)
{
if (calc[l][r])
return dp[l][r];
if (mn[l][r]>=l && mx[l][r]<=r)
return {l,r};
calc[l][r]=1;
if (mx[l][r]>r)
return dp[l][r]=solve(l,mx[l][r]);
return dp[l][r]=solve(mn[l][r],r);
}
long long minimum_walk(vector<int> pp,int s)
{
p=pp;
int n=p.size(),tl=0,tr=n-1;
long long ans=0;
for (int i=0;i<n;i++)
{
ans+=abs(p[i]-i);
mn[i][i]=p[i];
mx[i][i]=p[i];
for (int j=i+1;j<n;j++)
{
mn[i][j]=min(mn[i][j-1],p[j]);
mx[i][j]=max(mx[i][j-1],p[j]);
}
}
if (!ans)
return 0;
queue<pair<int,int> > q;
q.push(solve(s,s));
while (!q.empty())
{
auto cp=q.front();
q.pop();
if (cp.first)
{
auto np=solve(cp.first-1,cp.second);
if (!dist[np.first][np.second])
{
dist[np.first][np.second]=dist[cp.first][cp.second]+1;
q.push(np);
}
}
if (cp.second!=n-1)
{
auto np=solve(cp.first,cp.second+1);
if (!dist[np.first][np.second])
{
dist[np.first][np.second]=dist[cp.first][cp.second]+1;
q.push(np);
}
}
}
while (tl<s && p[tl]==tl)
tl++;
while (tr>s && p[tr]==tr)
tr--;
return ans+2*dist[tl][tr];
}
