#include "books.h"
#include <bits/stdc++.h>
using namespace std;
struct cycle { int l, r; };
long long minimum_walk(std::vector<int> p, int s) {
long long d = 0;
int n = p.size();
for (int i = 0; i < n; ++i) {
d += abs(p[i] - i);
}
vector<int> c(p.size(), -1);
vector<cycle> cycles;
int sl=s, sr=s;
for (int i = 0; i < n; ++i) {
if (c[i] != -1) continue;
if (p[i] == i) continue;
int x = i;
int l=x, r=x;
c[x] = cycles.size();
while ((x=p[x]) != i) {
c[x] = cycles.size();
l = min(l, x);
r = max(r, x);
}
if (l <= s && r >= s){
sl = min(l, sl);
sr = max(r, sr);
}
cycles.push_back({l, r});
}
int l=s, r=s; // already covered
int lx=s, rx=s; // free extension
if (c[s] != -1) {
lx = cycles[c[s]].l;
rx = cycles[c[s]].r;
}
while (l > sl || r < sr) {
if (l-1 >= 0 && l-1 >= lx)
--l;
else if (r+1 < n && r+1 <= rx)
++r;
else {
l = max(0, l-1);
r = min(r+1, n-1);
d += 2;
}
if (c[l] != -1) {
lx = min(lx, cycles[c[l]].l);
rx = max(rx, cycles[c[l]].r);
}
if (c[r] != -1) {
lx = min(lx, cycles[c[r]].l);
rx = max(rx, cycles[c[r]].r);
}
}
while (r+1 < n) {
++r;
if (c[r]==-1) continue;
if (cycles[c[r]].l != cycles[c[r]].r) {
d += 2*max(0, r - rx);
rx = max(rx, cycles[c[r]].r);
}
}
while (l-1 >= 0) {
--l;
if (c[l]==-1) continue;
if (cycles[c[l]].l != cycles[c[l]].r) {
d += 2*max(0, lx - l);
lx = min(lx, cycles[c[l]].l);
}
}
return d;
}
