//Cgrader.cpp
#include "books.h"
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define all(x) begin(x), end(x)
#define sz(x) ((int) (x).size())
using ll = long long;
using ld = long double;
const int N = 1e6 + 10;
int cc[N], cnt[N];
vector<tuple<int, int, int>> edges;
struct DSU {
int rank[N], parent[N];
DSU() {
iota(all(parent), 0);
}
int get(int u) {
if (u == parent[u]) {
return u;
}
return parent[u] = get(parent[u]);
}
bool merge(int a, int b) {
a = get(a);
b = get(b);
if (a == b) {
return false;
}
if (rank[a] == rank[b]) {
++rank[a];
}
if (rank[a] < rank[b]) {
swap(a, b);
}
parent[b] = a;
return true;
}
} dsu;
ll minimum_walk(vector<int> p, int s) {
int n = sz(p), m = 0;
ll ans = 0;
fill(all(cc), -1);
for (int i = 0; i < n; ++i) {
ans += abs(p[i] - i);
if (cc[i] == -1) {
int j = i;
while (cc[j] == -1) {
cc[j] = m;
cnt[m]++;
j = p[j];
}
++m;
}
}
// cout << ans << endl;
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
if (cc[i] != cc[j]) {
edges.push_back({abs(i - j), cc[i], cc[j]});
}
}
}
for (int i = 0; i < n; ++i) {
for (int j = min(p[i], i); j < max(p[i], i); ++j) {
if (cc[i] != cc[j]) {
edges.push_back({0, cc[i], cc[j]});
}
}
}
sort(all(edges));
for (auto [w, u, v] : edges) {
if (cnt[u] == 1 && u != cc[s]) {
continue;
}
if (cnt[v] == 1 && v != cc[s]) {
continue;
}
if (dsu.merge(u, v)) {
ans += 2 * w;
}
}
return ans;
}
