#include <bits/stdc++.h>
#include "books.h"
using namespace std;
#define Fi first
#define Se second
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define szz(x) (int)(x).size()
#define rep(i, n) for(int i=0;i<(n);i++)
typedef tuple<int, int, int> t3;
int c[1000010];
ll minimum_walk(vector<int> p, int s) {
int n = szz(p);
int l = s, r = s;
ll ans = 0;
rep(i, n) ans += abs(i - p[i]);
auto expend = [&]() {
for(int x=1;r+x<n || l-x>=0; x++) {
if(l-x >= 0 && p[l-x] != l-x) return -x;
if(r+x < n && p[r+x] != r+x) return x;
}
return 0;
};
vector <int> q; q.pb(s);
auto push = [&](int x) {
if(l > x) {
for(int a=l-1;a>=x;a--) q.pb(a);
l = x;
}
if(r < x) {
for(int a=r+1;a<=x;a++) q.pb(a);
r = x;
}
};
while(1) {
rep(i, szz(q)) {
int t = q[i];
if(c[t]) continue;
c[t] = 1;
for(int x=p[t];x!=t;x=p[x]) {
push(x);
c[x] = 1;
}
}
int d = expend();
if(d == 0) break;
q.clear();
ans += 2 * abs(d);
if(d < 0) push(l + d);
else push(r + d);
}
return ans;
}
