#include "books.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1'000'005;
int cyc[MAXN], lc[MAXN], rc[MAXN];
void extend(int &cl, int &cr, int tl, int tr){
while (cl > tl || cr < tr){
if (cl > tl){
cl--;
tl = min(tl, lc[cyc[cl]]); tr = max(tr, rc[cyc[cl]]);
}
else{
cr++;
tl = min(tl, lc[cyc[cr]]); tr = max(tr, rc[cyc[cr]]);
}
}
}
ll minimum_walk(vector<int> p, int s) {
int nums = p.size();
int mn = s, mx = s;
memset(cyc, -1, sizeof(cyc));
ll ans = 0;
for (int i = 0; i < nums; i++) ans += abs(i - p[i]);
for (int i = 0; i < nums; i++)
if (cyc[i] == -1){
int curr = i, l = i, r = i;
do{
cyc[curr] = i; l = min(l, curr); r = max(r, curr);
curr = p[curr];
} while (curr != i);
lc[i] = l; rc[i] = r;
if (p[i] != i){
mn = min(mn, l); mx = max(mx, r);
}
}
int cl = s, cr = s;
extend(cl, cr, lc[cyc[s]], rc[cyc[s]]);
while (cl > mn || cr < mx){
int lnl = cl, lnr = cr, le = 0;
while (lnl > mn && lnr <= cr){
extend(lnl, lnr, lnl - 1, lnr);
le++;
}
int rnl = cl, rnr = cr, re = 0;
while (rnr < mx && rnl >= cl){
extend(rnl, rnr, rnl, rnr + 1);
re++;
}
if (lnl == rnl && lnr == rnr){ // cross the middle
ans += 2 * min(le, re);
cl = lnl; cr = lnr;
}
else{
ans += 2 * (le + re);
cl = lnl; cr = rnr;
}
}
return ans;
}
