#include "books.h"
#include <bits/stdc++.h>
using namespace std;
#define sig signed
#define int long long
#define arr array
#define vec vector
const int N = 1e6 + 5, INF = 1e18;
int n, st;
arr<int, N> out;
arr<bool, N> vs;
int nm;
arr<vec<int>, N> cyc;
arr<int, N> lf, rg;
void dfs(int u) {
vs[u] = true;
cyc[nm].push_back(u), lf[nm] = min(lf[nm], u), rg[nm] = max(rg[nm], u);
if (vs[out[u]]) return;
dfs(out[u]);
}
int cyc_cmp() {
for (int u = 0; u < n; u++) {
if (vs[u]) continue;
nm++, lf[nm] = INF, rg[nm] = -1;
dfs(u);
}
int ans = 0;
for (int i = 1; i <= nm; i++) {
for (int j = 0; j < cyc[i].size(); j++) {
int k = (j + 1) % cyc[i].size();
ans += abs(cyc[i][j] - cyc[i][k]);
}
}
// for (int i = 1; i <= nm; i++) {
// cout << i << ": " << mn[i] << " " << mx[i] << endl;
// for (int u : cyc[i]) cout << u << " ";
// cout << endl;
// }
return ans;
}
vec<vec<int>> edg;
void edg_cmp() {
for (int i = 1; i <= nm; i++) {
for (int j = 1; j <= nm; j++) {
if (i == j) continue;
int dst = 0;
if (lf[j] > rg[i]) dst = 2 * (lf[j] - rg[i]);
if (lf[j] < lf[i]) dst = 2 * (lf[i] - lf[j]);
edg.push_back({dst, i, j});
}
}
sort(edg.begin(), edg.end());
}
struct Dsj {
arr<int, N> prnt;
void intl() {
for (int u = 1; u <= nm; u++) prnt[u] = u;
}
int pr(int u) {
return (prnt[u] == u) ? u : prnt[u] = pr(prnt[u]);
}
bool mrg(int u, int v) {
u = pr(u), v = pr(v);
if (u == v) return false;
prnt[v] = u;
return true;
}
} dsj;
int dsj_cmp() {
dsj.intl();
int ans = 0;
for (vec<int> x : edg) {
int cst = x[0], u = x[1], v = x[2];
if (!dsj.mrg(u, v)) continue;
ans += cst;
}
return ans;
}
int minimum_walk(vec<sig> _out, sig _st) {
n = _out.size(), st = _st;
for (int u = 0; u < n; u++) out[u] = _out[u];
int ans = cyc_cmp();
edg_cmp();
ans += dsj_cmp();
return ans;
}
