#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 = array<int, 2>;
using ll = long long;
void unite(ii &a, ii b) {
a[0] = min(a[0], b[0]), a[1] = max(a[1], b[1]);
}
ll minimum_walk(vi p, int s) {
const int n = sz(p);
vector<ii> range;
vi cycle(n);
vector<bool> vis(n, false);
forn(i, n) {
if (vis[i]) continue;
int j = i;
ii currRange = {j, j};
while (!vis[j]) {
vis[j] = true;
cycle[j] = sz(range);
unite(currRange, ii{j, j});
j = p[j];
}
range.pb(currRange);
}
const int c = sz(range);
ll ret = 0;
forn(i, n) ret += abs(i - p[i]);
ii need = {s, s};
forn(i, c) {
if (range[i][0] == range[i][1]) continue;
unite(need, range[i]);
}
const ii diff = {-1, 1};
auto extend = [&](ii &currRange) {
ii newRange = currRange;
forn(t, 2) unite(newRange, range[cycle[currRange[t]]]);
while (currRange != newRange) {
forn(t, 2) if (newRange[t] != currRange[t]) {
currRange[t] += diff[t];
unite(newRange, range[cycle[currRange[t]]]);
}
}
};
ii currRange = {s, s};
extend(currRange);
while (currRange[0] > need[0] || currRange[1] < need[1]) {
ii cost = {0, 0};
bool flag[2] = {false, false};
ii nextRange = currRange;
forn(t, 2) {
ii newRange = currRange;
while (newRange[t] * diff[t] < need[t] * diff[t] && newRange[1 - t] == currRange[1 - t]) {
newRange[t] += diff[t]; extend(newRange); cost[t] += 2;
}
flag[t] = !(newRange[1 - t] == currRange[1 - t]);
unite(nextRange, newRange);
}
assert(flag[0] == flag[1]);
if (flag[0]) ret += min(cost[0], cost[1]);
else ret += cost[0] + cost[1];
currRange = nextRange;
extend(currRange);
}
return ret;
}
