#include <bits/stdc++.h>
#include "books.h"
using std::vector;
using std::array;
using std::pair;
using std::tuple;
using ll = long long;
struct UnionFind {
vector<int> par;
UnionFind(const int n) : par(n, -1) {}
int find(const int u) {
return par[u] < 0 ? u : par[u] = find(par[u]);
}
void merge(int u, int v) {
u = find(u), v = find(v);
if (u == v) return;
if (par[u] > par[v]) std::swap(u, v);
par[u] += par[v];
par[v] = u;
return;
}
};
ll minimum_walk(vector<int> P, int src) {
{
int l = 0;
while (l < src and P[l] == l) l += 1;
int r = (int)P.size() - 1;
while (r > src and P[r] == r) r -= 1;
P.erase(P.begin() + r + 1, P.end());
P.erase(P.begin(), P.begin() + l);
for (auto& x : P) x -= l;
src -= l;
}
const int N = P.size();
vector<vector<int>> cycle;
{
vector<char> done(N);
for (int i = 0; i < N; ++i) {
if (done[i]) continue;
auto& v = cycle.emplace_back();
for (int j = i; !done[j]; j = P[j]) {
v.push_back(j);
done[j] = true;
}
}
}
const int M = cycle.size();
UnionFind dsu(M);
{
vector<vector<int>> list(2 * N);
const auto process = [&](int k, const int i) {
while (k > 0) {
for (const int j : list[k]) dsu.merge(i, j);
list[k] = {i};
k >>= 1;
}
};
for (int i = 0; i < M; ++i) {
auto& v = cycle[i];
std::sort(v.begin(), v.end());
for (int j = 1; j < (int)v.size(); ++j) {
const int lc = N + v[j - 1];
const int rc = N + v[j];
for (int l = lc, r = rc; l < r; l >>= 1, r >>= 1) {
if (l & 1) list[l++].push_back(i);
if (r & 1) list[--r].push_back(i);
}
process(lc, i);
process(rc, i);
}
}
}
vector<int> belongs(N);
for (int i = 0; i < M; ++i) {
const int p = dsu.find(i);
for (const int j : cycle[i]) {
belongs[j] = p;
}
}
vector<vector<int>> list(M);
for (int i = 0; i < N; ++i) list[belongs[i]].push_back(i);
vector<int> parent(M, -1);
{
vector<int> start(N, -1), end(N, -1);
for (int j = 0; j < M; ++j) {
if (!list[j].empty()) {
start[list[j].front()] = j;
end[list[j].back()] = j;
}
}
vector<int> stack;
for (int i = 0; i < N; ++i) {
if (start[i] != -1) {
if (!stack.empty()) parent[start[i]] = stack.back();
stack.push_back(start[i]);
}
if (end[i] != -1) stack.pop_back();
}
}
vector<int> dist(M, N + 1);
{
std::queue<int> que;
const auto push = [&](const int u, const int d) {
if (dist[u] > d) {
dist[u] = d;
que.push(u);
}
};
push(belongs[src], 0);
while (!que.empty()) {
const int u = que.front();
que.pop();
const int l = list[u].front();
const int r = list[u].back();
if (l > 0) push(belongs[l - 1], dist[u] + 1);
if (r + 1 < N) push(belongs[r + 1], dist[u] + 1);
}
}
int root = belongs[src];
while (parent[root] != -1) root = parent[root];
ll ret = 2 * dist[root];
vector<int> coeff(N);
for (int i = 0; i < N; ++i) {
const int l = std::min(i, P[i]);
const int r = std::max(i, P[i]);
ret += r - l;
coeff[l] += 1;
coeff[r] -= 1;
}
for (int i = 0; i < N - 1; ++i) {
if (coeff[i] == 0) ret += 2;
coeff[i + 1] += coeff[i];
}
return ret;
}
