#include "books.h"
#include <bits/stdc++.h>
#define forsn(i, s, n) for (int i = int(s); i < int(n); i++)
#define forn(i, n) forsn(i, 0, n)
#define dforsn(i, s, n) for (int i = int(n) - 1; i >= int(s); i--)
#define dforn(i, n) dforsn(i, 0, n)
#define sz(x) int(x.size())
#define all(x) begin(x), end(x)
#define pb push_back
#define eb emplace_back
#define fst first
#define snd second
using namespace std;
using vi = vector<int>;
using ii = pair<int, int>;
using ll = long long;
ll minimum_walk(vi p, int s) {
const int n = sz(p);
vi L, R;
vi cycle(n);
vector<bool> vis(n, false);
forn(i, n) {
if (vis[i]) continue;
int j = i, l = i, r = i;
while (!vis[j]) {
vis[j] = true;
cycle[j] = sz(L);
l = min(l, j);
r = max(r, j);
j = p[j];
}
L.pb(l), R.pb(r);
}
const int c = sz(L);
ll ret = 0;
forn(i, n) ret += abs(i - p[i]);
int needL = s, needR = s;
forn(i, c) {
if (L[i] == R[i]) continue;
needL = min(needL, L[i]);
needR = max(needR, R[i]);
}
auto extend = [&](int &l, int &r) {
int newL = l;
int newR = r;
auto update = [&](int id) {
newL = min(newL, L[id]);
newR = max(newR, R[id]);
};
update(cycle[l]);
update(cycle[r]);
while (newL < l || newR > r) {
if (newL < l) update(cycle[--l]);
if (newR > r) update(cycle[++r]);
}
};
int l = s, r = s;
extend(l, r);
while (l > needL || r < needR) {
int leftCost = 0, rightCost = 0;
bool flag = false;
int newL = l, newR = r;
while (newL > needL && newR == r) {
newL--; extend(newL, newR);
leftCost += 2;
}
flag = newR > r;
int nextL = newL, nextR = newR;
newL = l, newR = r;
while (newR < needR && newL == l) {
newR++; extend(newL, newR);
rightCost += 2;
}
nextL = min(nextL, newL);
nextR = max(nextR, newR);
assert(flag == (newL < l));
if (flag) {
ret += min(leftCost, rightCost);
} else {
ret += leftCost + rightCost;
}
l = nextL, r = nextR;
extend(l, r);
}
return ret;
}
