#include "books.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
using vint = vector<int>;
using vll = vector<ll>;
using vld = vector<ld>;
using vpii = vector<pii>;
using vpil = vector<pil>;
using vpli = vector<pli>;
using vpll = vector<pll>;
#define x first
#define y second
#define all(v) v.begin(),v.end()
ll minimum_walk(vint p, int s) {
int n = p.size();
vint cnum(n), lp(1), rp(1);
int cnt = 0;
ll ans = 0;
for(int i = 0; i < n; i++) {
if(cnum[i] || p[i] == i) continue;
cnt++;
int x = i;
lp.push_back(i);
rp.push_back(i);
do {
ans += abs(x - p[x]);
x = p[x];
lp[cnt] = min(lp[cnt], x);
rp[cnt] = max(rp[cnt], x);
cnum[x] = cnt;
} while(x != i);
}
int ls = s, rs = s;
vpii seg;
for(int i = 1; i <= cnt; i++) seg.emplace_back(lp[i], rp[i]);
sort(all(seg), [&](pii &p, pii &q){ return p.y > q.y; });
for(pii &p : seg) if(ls <= p.y) ls = min(ls, p.x);
sort(all(seg), [&](pii &p, pii &q){ return p.x < q.x; });
for(pii &p : seg) if(p.x <= rs) rs = max(rs, p.y);
vint d(n, n);
priority_queue<pii, vector<pii>, greater<pii>> pq;
set<int> cand[2];
for(int i = ls; i <= rs; i++) { cand[0].insert(i); cand[1].insert(i); }
auto put = [&](int l, int r, int c, int a) {
auto &cc = cand[a];
auto it = cc.lower_bound(l);
while(it != cc.end() && *it <= r) {
int x = *it;
it++;
cc.erase(x);
if(d[x] > c + a) {
d[x] = c + a;
pq.emplace(c + a, x);
}
}
};
put(s, s, 0, 0);
while(!pq.empty()) {
pii c = pq.top();
pq.pop();
if(d[c.y] != c.x) continue;
if(c.y == ls || c.y == rs) {
ans += 2 * c.x;
break;
}
if(cnum[c.y]) put(lp[cnum[c.y]], rp[cnum[c.y]], c.x, 0);
if(c.y > 0) put(c.y - 1, c.y - 1, c.x, 1);
if(c.y < n - 1) put(c.y + 1, c.y + 1, c.x, 1);
}
vpii lseg;
for(int i = 1; i <= cnt; i++) if(rp[i] < ls) lseg.emplace_back(lp[i], rp[i]);
sort(all(lseg), [&](pii &p, pii &q){ return p.y > q.y; });
for(pii &p : lseg) {
if(p.y < ls) ans += 2 * (ls - p.y);
ls = min(ls, p.x);
}
vpii rseg;
for(int i = 1; i <= cnt; i++) if(rs < lp[i]) rseg.emplace_back(lp[i], rp[i]);
sort(all(rseg), [&](pii &p, pii &q){ return p.x < q.x; });
for(pii &p : rseg) {
if(rs < p.x) ans += 2 * (p.x - rs);
rs = max(rs, p.y);
}
return ans;
}
