#include "books.h"
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
vector<vector<int>> adj;
vector<int> dist;
long long minimum_walk(vector<int> p, int s) {
ll tot = 0;
int n = p.size();
vector<bool> taken(n, false);
int g = n;
adj.resize(n);
for(int i = 1; i < n; i++) {
adj[i].push_back(i-1);
adj[i-1].push_back(i);
}
for(int i = 0; i < n; i++) {
if(!taken[i]) {
adj.push_back(vector<int>());
int x = i;
int l = i, r = i;
while(!taken[x]) {
taken[x] = true;
tot += abs(x - p[x]);
x = p[x];
l = min(l, x);
r = max(r, x);
adj[x].push_back(g);
}
for(int j = l; j <= r; j++) {
adj[g].push_back(j);
}
g++;
}
}
dist.resize(g, 1e9 + 7);
int best = 0;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
pq.push({0, s});
while(pq.size()) {
auto p = pq.top();
pq.pop();
int len = p.first, x = p.second;
if(len > dist[x]) continue;
best = max(best, len);
for(int ch : adj[x]) {
int goLength;
if(max(ch, x) < n) {
goLength = len + 1;
}
else {
goLength = len;
}
if(dist[ch] <= goLength) continue;
dist[ch] = goLength;
pq.push({goLength, ch});
}
}
return tot + 2 * best;
}
