#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define lg length()
#define pb push_back
#define INF 2000000005
#define LINF 1000000000000000005
#define all(x) (x).begin(), (x).end()
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rand(int l,int r){return uniform_int_distribution<int>(l,r)(rng);}
#include "books.h"
long long minimum_walk(vector<int> p, int s) {
long long sum = 0;
int L = -1,R = -1;
int n = sz(p);
for(int i=0;i<n;i++) sum += abs(i - p[i]);
for(int i=0;i<n;i++){
if(p[i]!=i){
L = i;
break;
}
}
if(L == -1) return 0;
for(int i=n-1;i>=0;i--){
if(p[i]!=i){
R = i;
break;
}
}
L = min(L, s);
R = max(R, s);
vector<int> v(n, 0);
int l=s,r=s;
queue<int> q;
q.push(s);
long long ans = 0;
while(l != L || r != R){
while(q.size()){
int i = q.front();
q.pop();
if(!v[i]){
int ln=i,rn=i;
v[i] = 1;
int j = p[i];
while(j != i){
v[j] = 1;
ln = min(ln, j);
rn = max(rn, j);
j = p[j];
}
for(int j=ln;j<l;j++) q.push(j);
for(int j=r+1;j<=rn;j++) q.push(j);
l = min(l, ln); r = max(r, rn);
}
}
long long cl = 0, cr = 0;
vector<int> qL, qR;
int sl = -1, sr = -1;
int oldl = l, oldr = r;
while(l != L){
l--;
q.push(l);
cl += 2;
while(q.size()){
int i = q.front();
q.pop();
if(!v[i]){
int ln=i,rn=i;
v[i] = 1;
qL.push_back(i);
int j = p[i];
while(j != i){
v[j] = 1;
qL.push_back(j);
ln = min(ln, j);
rn = max(rn, j);
j = p[j];
}
if(rn > r){
sl = i;
break;
}
for(int j=ln;j<l;j++) q.push(j);
for(int j=r+1;j<=rn;j++) q.push(j);
l = min(l, ln); r = max(r, rn);
}
}
if(sl != -1) break;
}
for(int i : qL) v[i] = 0;
while(sz(q)) q.pop();
l = oldl; r = oldr;
while(r != R){
r++;
q.push(r);
cr += 2;
while(q.size()){
int i = q.front();
q.pop();
if(!v[i]){
int ln=i,rn=i;
v[i] = 1;
qL.push_back(i);
int j = p[i];
while(j != i){
v[j] = 1;
qL.push_back(j);
ln = min(ln, j);
rn = max(rn, j);
j = p[j];
}
if(ln < l){
sr = i;
break;
}
for(int j=ln;j<l;j++) q.push(j);
for(int j=r+1;j<=rn;j++) q.push(j);
l = min(l, ln); r = max(r, rn);
}
}
if(sr != -1) break;
}
for(int i : qR) v[i] = 0;
while(sz(q)) q.pop();
l = oldl; r = oldr;
if(sl == -1){
ans += cl + cr;
break;
}
else{
if(cl < cr) ans += cl, q.push(sl);
else ans += cr, q.push(sr);
}
}
return ans + sum;
}
