#include "books.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1000 + 10;
bool visited[maxn];
int c[maxn], l[maxn], r[maxn];
int n;
int dp[maxn][maxn], mr[maxn][maxn], ml[maxn][maxn];
long long minimum_walk(vector<int> p, int s){
n = p.size();
ll answer = 0;
for (int i = 0; i < n; i++)
answer += abs(p[i]-i);
memset(r, -1, sizeof r);
memset(l, 63, sizeof l);
for (int i = 0; i < n; i++){
if (!visited[i]){
int x = i;
while (!visited[x]){
visited[x] = 1;
c[x] = i;
r[i] = max(r[i],x);
l[i] = min(l[i],x);
x = p[x];
}
x = p[x];
while (x != i){
l[x] = l[i], r[x] = r[i];
x = p[x];
}
}
}
ml[s][s] = l[s];
mr[s][s] = r[s];
for (int i = s; i >= 0; i--){
for (int j = s; j < n; j++){
if (i == s and j == s)
continue;
ml[i][j] = n;
if (i < s)
ml[i][j] = min(l[i], ml[i+1][j]), mr[i][j] = max(r[i], mr[i+1][j]);
if (j > s)
ml[i][j] = min(l[j], ml[i][j-1]), mr[i][j] = max(r[j], mr[i][j-1]);
}
}
memset(dp, 63, sizeof dp);
dp[s][s] = 0;
for (int i = s; i >= 0; i--){
for (int j = s; j < n; j++){
if (j < n-1)
dp[i][j+1] = min(dp[i][j+1], dp[i][j] + (mr[i][j] <= j));
if (i > 0)
dp[i-1][j] = min(dp[i-1][j], dp[i][j] + (ml[i][j] >= i));
}
}
int fi = s, se = s;
for (int i = 0; i < n; i++){
if (p[i] != i){
fi = min(fi,i);
se = max(se,i);
}
}
dp[n][0] = 0;
return answer + 2LL*dp[fi][se];
}
