#include "books.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> p;
vector<pair<int,int> > c,d;
pair<int,int> dp[1005][1005];
bool vis[1005],calc[1005][1005];
int cyc[1005],dist[1005][1005];
void dfs(int i)
{
vis[i]=1;
auto &x=c[c.size()-1];
x.first=min(x.first,i);
x.second=max(x.second,i);
cyc[i]=c.size()-1;
if (!vis[p[i]])
dfs(p[i]);
}
pair<int,int> Union(pair<int,int> a,pair<int,int> b)
{
return {min(a.first,b.first),max(a.second,b.second)};
}
pair<int,int> solve(int l,int r)
{
if (calc[l][r])
return dp[l][r];
calc[l][r]=1;
return dp[l][r]=Union(solve(l,r-1),solve(r,r));
}
long long minimum_walk(vector<int> pp,int s)
{
p=pp;
while (!p.empty() && p.back()+1==p.size())
p.pop_back();
int n=p.size();
if (!n)
return 0;
long long ans=0;
for (int i=0;i<n;i++)
{
calc[i][i]=1;
ans+=abs(p[i]-i);
if (!vis[i])
{
c.push_back({i,i});
dfs(i);
}
}
sort(c.begin(),c.end());
for (auto x:c)
{
if (d.empty() || x.first>d.back().second)
d.push_back(x);
else
d[d.size()-1].second=max(d[d.size()-1].second,x.second);
}
for (auto x:d)
{
for (int i=x.first;i<=x.second;i++)
dp[i][i]=x;
}
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);
}
}
}
return ans+2*dist[0][n-1];
}
