#include <bits/stdc++.h>
#include "books.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define sep ' '
#define X first
#define Y second
#define all(x) (x).begin() , (x).end()
#define SZ(x) int(x.size())
const int MAXN = 1e6 + 10;
ll n , s , sum , P[MAXN] , mark[MAXN] , L[MAXN] , R[MAXN] , ps[MAXN];
ll minimum_walk(vector<int> p, int S) {
n = SZ(p); s = S;
for(int i = 0 ; i < n ; i++){
P[i] = p[i];
sum += abs(P[i] - i);
}
int l = 0 , r = n - 1;
while(r > l && r > s && P[r] == r) r--;
while(l <= r && l < s && P[l] == l) l++;
if(l == r && P[l] == P[r]){
return 0;
}
for(int i = l ; i <= r ; i++){
L[i] = R[i] = i;
}
for(int i = l ; i <= r ; i++){
if(!mark[i]){
vector<int> V;
int x = i;
while(!mark[x]){
mark[x] = 1;
V.push_back(x);
x = P[x];
}
sort(all(V));
for(int j = 0 ; j + 1 < SZ(V) ; j++){
int v = V[j] , u = V[j + 1];
R[v] = u; L[u] = v;
ps[v]++; ps[u]--;
}
}
}
partial_sum(ps , ps + MAXN , ps);
vector<int> comps;
for(int i = l ; i <= r ; i++){
if(ps[i] == 0){
comps.push_back(i);
}
}
int t = *lower_bound(all(comps) , s);
int curl = s , curr = s;
int mnl = L[s] , mxr = R[s];
ll ans = sum + SZ(comps) * 2 - 2;
while(1){
while(mnl != curl || mxr != curr){
if(mnl != curl){
curl--;
mnl = min((ll)mnl , L[curl]);
mxr = max((ll)mxr , R[curl]);
}
else{
curr++;
mnl = min((ll)mnl , L[curr]);
mxr = max((ll)mxr , R[curr]);
}
}
if(curr >= t){
break;
}
ans += 2;
curl--;
mnl = min((ll)mnl , L[curl]);
mxr = max((ll)mxr , R[curl]);
curr++;
mnl = min((ll)mnl , L[curr]);
mxr = max((ll)mxr , R[curr]);
}
return ans;
}
