//Cgrader.cpp
#include "books.h"
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define all(x) begin(x), end(x)
#define sz(x) ((int) (x).size())
using ll = long long;
using ld = long double;
const int N = 1e3 + 10, INF = 0x3f3f3f3f;
int cc[N], cnt[N], clef[N], crig[N];
pair<int, int> q[N][N];
int dp[N][N];
ll minimum_walk(vector<int> p, int s) {
int rl = 0, rr = sz(p);
while (rl < s) {
if (p[rl] == rl) {
++rl;
} else {
break;
}
}
while (rr > s + 1) {
if (p[rr - 1] == rr - 1) {
--rr;
} else {
break;
}
}
p = vector(begin(p) + rl, begin(p) + rr);
s -= rl;
for (int &u : p) {
u -= rl;
}
int n = sz(p), m = 0;
ll ans = 0;
fill(all(cc), -1);
for (int i = 0; i < n; ++i) {
ans += abs(p[i] - i);
if (cc[i] == -1) {
clef[m] = crig[m] = i;
int j = i;
while (cc[j] == -1) {
cc[j] = m;
cnt[m]++;
crig[m] = max(crig[m], j);
j = p[j];
}
++m;
}
}
for (int i = 0; i < n; ++i) {
q[i][i] = {clef[cc[i]], crig[cc[i]]};
for (int j = i + 1; j < n; ++j) {
q[i][j].x = min(q[i][j - 1].x, clef[cc[j]]);
q[i][j].y = max(q[i][j - 1].y, crig[cc[j]]);
}
}
for (int len = n - 1; len > 0; --len) {
for (int i = 0; i <= n - len; ++i) {
int j = i + len - 1;
if (q[i][j] != pair{i, j}) {
// cout << "at " << i << " " << j << ", extending to " << q[i][j].x << " " << q[i][j].y << endl;
dp[i][j] = dp[q[i][j].x][q[i][j].y];
} else {
dp[i][j] = +INF;
if (i) {
dp[i][j] = dp[i - 1][j] + 2;
}
if (j != n - 1) {
dp[i][j] = min(dp[i][j], dp[i][j + 1] + 2);
}
}
}
}
return ans + dp[s][s];
}
