#include <bits/stdc++.h>
#include "books.h"
using std::vector;
using std::array;
using std::pair;
using std::tuple;
using ll = long long;
ll minimum_walk(vector<int> P, int src) {
{
int l = 0;
while (l < src and P[l] == l) {
l += 1;
}
int r = (int)P.size() - 1;
while (r > src and P[r] == r) {
r -= 1;
}
src -= l;
P.erase(P.begin() + r + 1, P.end());
P.erase(P.begin(), P.begin() + l);
}
const int N = P.size();
assert(N <= 1000);
vector<int> min(N), max(N);
vector<char> done(N);
ll ret = 0;
for (int i = 0; i < N; ++i) {
if (!done[i]) {
vector<int> list;
for (int j = i; !done[j]; j = P[j]) {
list.push_back(j);
ret += std::abs(P[j] - j);
done[j] = true;
}
const int l = *std::min_element(list.begin(), list.end());
const int r = *std::max_element(list.begin(), list.end());
for (const int j : list) {
min[j] = l;
max[j] = r;
}
}
}
vector dist(N, vector(N, N + 1));
std::deque<pair<int, int>> que;
const auto push0 = [&](const int l, const int r, const int d) {
if (dist[l][r] > d) {
dist[l][r] = d;
que.emplace_front(l, r);
}
};
const auto push1 = [&](const int l, const int r, const int d) {
if (dist[l][r] > d + 1) {
dist[l][r] = d + 1;
que.emplace_back(l, r);
}
};
push0(src, src, 0);
while (!que.empty()) {
const auto [l, r] = que.front();
que.pop_front();
push0(std::min({l, min[l], min[r]}), std::max({r, max[l], max[r]}), dist[l][r]);
if (l < r) {
push0(l + 1, r, dist[l][r]);
push0(l, r - 1, dist[l][r]);
}
if (l > 0) {
push1(l - 1, r, dist[l][r]);
}
if (r + 1 < N) {
push1(l, r + 1, dist[l][r]);
}
}
return ret + 2 * dist[0][N - 1];
}
