// #include "books.h"
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define all(arr) (arr).begin(), (arr).end()
#define ll long long
#define ld long double
#define pb push_back
#define sz(x) (int)(x).size()
#define fi first
#define se second
#define endl '\n'
const int N = 1e6 + 20, INF = 1e9;
int t[4 * N];
void modify(int v, int tl, int tr, int pos, int val){
if (tl == tr){
t[v] = val;
return;
}
int tm = (tl + tr) / 2;
if (pos <= tm) modify(2 * v + 1, tl, tm, pos, val);
else modify(2 * v + 2, tm + 1, tr, pos, val);
t[v] = min(t[2 * v + 1], t[2 * v + 2]);
}
int query(int v, int tl, int tr, int l, int r){
if (l > r) return INF;
if (tl == l && tr == r) return t[v];
int tm = (tl + tr) / 2;
return min(
query(2 * v + 1, tl, tm, l, min(r, tm)),
query(2 * v + 2, tm + 1, tr, max(l, tm + 1), r)
);
}
long long minimum_walk(std::vector<int> p, int s) {
int n = sz(p);
ll ans = 0;
for (int i = 0; i < n; i++){
ans += abs(i - p[i]);
}
int mincycle = -1, maxcycle = -1;
for (int i = 0; i < n; i++) if (i != p[i]){
mincycle = i;
break;
}
for (int i = n - 1; i >= 0; i--) if (i != p[i]){
maxcycle = i;
break;
}
if (mincycle == -1) return 0;
for (int i = mincycle, mx = -1; i < n;){
mx = max(mx, p[i]);
if (mx <= i){
int j = i + 1;
while (j < n && j == p[j]) j++;
if (j == n) break;
ans += 2 * (j - i), i = j;
}
else i++;
}
if (s < mincycle) return ans + 2 * (mincycle - s);
if (s > maxcycle) return ans + 2 * (s - maxcycle);
vector<bool> cycleend(n);
for (int i = 0, mx = -1; i < n; i++){
mx = max(mx, p[i]);
if (mx <= i) cycleend[i] = 1;
}
vector<int> cur, used(n), cid(n), minpos(n, INF), maxpos(n, -1);
vector<int> minl(n, INF), maxr(n, -1);
vector<vector<int>> has(n);
int id = 0;
function<void(int)> dfs = [&] (int v){
used[v] = 1, cid[v] = id;
minpos[id] = min(minpos[id], v);
maxpos[id] = max(maxpos[id], v);
has[id].pb(v);
if (!used[p[v]]) dfs(p[v]);
};
for (int i = 0; i < n; i++){
if (used[i]) continue;
dfs(i);
id++;
}
vector<int> order(id);
iota(all(order), 0);
sort(all(order), [&] (int i, int j){
return minpos[i] < minpos[j];
});
for (int i = 0; i < 4 * n; i++) t[i] = INF;
for (auto i : order){
minl[i] = min(minpos[i], query(0, 0, n - 1, minpos[i], maxpos[i]));
for (auto v : has[i]) modify(0, 0, n - 1, v, minl[i]);
}
sort(all(order), [&] (int i, int j){
return maxpos[i] > maxpos[j];
});
for (int i = 0; i < 4 * n; i++) t[i] = INF;
for (auto i : order){
maxr[i] = max(maxpos[i], -query(0, 0, n - 1, minpos[i], maxpos[i]));
for (auto v : has[i]) modify(0, 0, n - 1, v, -maxr[i]);
}
int startl = s, startr = s;
while (startl > 0 && !cycleend[startl - 1]) startl--;
while (!cycleend[startr]) startr++;
vector<int> pdp(n), sdp(n);
for (int i = startl + 1; i <= startr; i++){
int l = minl[cid[i]];
pdp[i] = (l <= startl? 0 : pdp[l - 1] + 1);
}
for (int i = startr - 1; i >= startl; i--){
int r = maxr[cid[i]];
sdp[i] = (r >= startr? 0 : sdp[r + 1] + 1);
}
int ans1 = INF;
for (int i = 0; i < id; i++){
if (minl[i] < startl || minl[i] > startr) continue;
int cur = INF;
for (auto x : has[i]) cur = min(cur, abs(s - x));
ans1 = min(ans1, cur + pdp[minl[i]] + sdp[maxr[i]]);
}
return ans + 2 * ans1;
}
