#include "books.h"
#include <bits/stdc++.h>
#define pb push_back
#define F first
#define S second
using namespace std;
using ll = long long int;
using pll = pair<ll, ll>;
using pii = pair<int, int>;
const int inf = 1.05e9;
const ll INF = 1e18;
ll minimum_walk(vector<int> p, int s) {
ll ans = 0, mx = 0, mx1 = 0, mx2 = 0;
int n = p.size(), l = s, r = s;
ll d[n], g[n];
memset(d, -1, sizeof d);
memset(g, -1, sizeof g);
d[s] = 0;
queue<int> q[2];
q[0].push(s);
while(true){
while(!q[0].empty()){
int v = q[0].front();
q[0].pop();
for(int i = p[v]; d[i] == -1; i = p[i]){
d[i] = d[v];
q[0].push(i);
}
while(l > v){
l--;
if(d[l] == -1){
d[l] = d[v];
q[0].push(l);
}
}
while(r < v){
r++;
if(d[r] == -1){
d[r] = d[v];
q[0].push(r);
}
}
if(v && g[v - 1] == -1){
g[v - 1] = d[v] + 1;
q[1].push(v - 1);
}
if(v + 1 < n && g[v + 1] == -1){
g[v + 1] = d[v] + 1;
q[1].push(v + 1);
}
}
if(q[1].empty()) break;
int v = q[1].front();
q[1].pop();
if(d[v] != -1) continue;
d[v] = g[v];
for(int i = p[v]; d[i] == -1; i = p[i]){
d[i] = d[v];
q[0].push(i);
}
while(l > v){
l--;
if(d[l] == -1){
d[l] = d[v];
q[0].push(l);
}
}
while(r < v){
r++;
if(d[r] == -1){
d[r] = d[v];
q[0].push(r);
}
}
if(v && g[v - 1] == -1){
g[v - 1] = d[v] + 1;
q[1].push(v - 1);
}
if(v + 1 < n && g[v + 1] == -1){
g[v + 1] = d[v] + 1;
q[1].push(v + 1);
}
}
for(int i = 0; i < n; i++){
ans += abs(i - p[i]);
if(i <= s && p[i] >= s) mx = max(mx, d[i]);
if(i <= s && i != p[i]) mx1 = max(mx1, d[i]);
if(i >= s && i != p[i]) mx2 = max(mx2, d[i]);
}
return ans + 2 * (mx1 + mx2 - mx);
}
