#include <bits/stdc++.h>
#include "books.h"
#define int long long
using namespace std;
const int maxn = 1e6 + 5, INF = 1e18;
int n;
int p[maxn], ll[maxn], rr[maxn], vis[maxn];
int fa[maxn], sz[maxn];
int rt(int u) {
if (fa[u] == u) return u;
return fa[u] = rt(fa[u]);
}
void merge(int u, int v) {
u = rt(u), v = rt(v);
if (u == v) return;
if (sz[u] > sz[v]) swap(u, v);
fa[u] = v;
sz[v] += sz[u];
ll[v] = min(ll[u], ll[v]);
rr[v] = max(rr[u], rr[v]);
}
int minimum_walk(vector<int32_t> P, int32_t S) {
n = P.size();
for (int i=0;i<n;i++) p[i+1] = P[i] + 1;
S++;
for (int i=0;i<=n+1;i++) ll[i] = rr[i] = fa[i] = i, sz[i] = 1;
int ans = 0, cnt = 0;
for (int i=1;i<=n;i++) if (!vis[i]) {
int u = i;
while (true) {
merge(u, i);
vis[u] = true;
int v = p[u];
ans += abs(v-u);
if (v==i) break;
u = v;
}
}
set<int> s;
s.insert(INF);
for (int i=1;i<=n;i++) if (ll[rt(i)] == i) {
int u = i, lim = rr[rt(i)];
vector<int> log;
while (s.size() > 0) {
int pos = *s.lower_bound(u);
if (pos > lim) break;
log.push_back(rt(pos));
u = rr[rt(pos)] + 1;
}
for (int j:log) merge(j, i);
u = i;
while (true) {
s.insert(u);
int v = p[u];
if (v == i) break;
u = v;
}
}
int lend = 1, rend = n;
while (lend+1 <= n && p[lend] == lend) lend++;
while (rend-1 >= 1 && p[rend] == rend) rend--;
int l = ll[rt(S)], r = rr[rt(S)];
if (l >= lend && r <= rend) {
merge(lend-1, rend+1);
while (l >= lend && r <= rend) {
int lcost = 0, rcost = 0;
int lu = l;
while (rr[rt(lu)] <= r) {
lu = ll[rt(lu - 1)], lcost += 2;
}
if (lu == lend-1) lcost = INF;
int ru = r;
while (ll[rt(ru)] >= l) {
ru = rr[rt(ru + 1)], rcost += 2;
}
if (ru == rend+1) rcost = INF;
// cout << l << " " << r << endl;
if (lcost == INF && rcost == INF) break;
if (lcost < rcost) ans += lcost, l = ll[rt(lu)], r = rr[rt(lu)];
else ans += rcost, l = ll[rt(ru)], r = rr[rt(ru)];
}
}
while (l > lend) l = ll[rt(l-1)], ans += 2;
while (r < rend) r = rr[rt(r+1)], ans += 2;
return ans;
}
