#include "books.h"
#include<bits/stdc++.h>
#define fr first
#define sc second
#define all(s) s.begin(), s.end()
using namespace std;
const int nmax = 1005;
long long n, comp, viz[nmax], l_ned, r_ned, ans;
pair<long long,long long>extend[nmax];
vector<long long>cicles[nmax];
pair<long long, long long>dp[nmax][nmax];
long long compute(long long L, long long R){
if(L <= l_ned && R >= r_ned) return 0LL;
else{
if(dp[L][R].sc == 1){
return dp[L][R].fr;
}
else{
dp[L][R].sc = 1;
dp[L][R].fr = 1e18;
if(L > 0){
dp[L][R].fr = compute(min(L-1, extend[viz[L-1]].fr), max(R, extend[viz[L-1]].sc)) + 2LL;
}
else if(R < n-1){
dp[L][R].fr = min(dp[L][R].fr, compute(min(L, extend[viz[R+1]].fr), max(R+1, extend[viz[R+1]].sc)) + 2LL);
}
return dp[L][R].fr;
}
}
}
long long minimum_walk(vector<int> p, int s) {
n = (int)p.size();
for(int i=0;i<n;i++){
ans += abs(i - p[i]);
}
for(int i=0;i<n;i++){
if(!viz[i]){
++comp;
viz[i] = comp;
cicles[comp].push_back(i);
int curr = p[i];
while(curr != i){
viz[curr] = comp;
cicles[comp].push_back(curr);
curr = p[curr];
}
}
}
for(int i=1;i<=comp;i++){
sort(all(cicles[i]));
}
for(int i=1;i<=comp;i++){
long long mini = cicles[i][0];
long long maxi = cicles[i].back();
for(int j=1;j<=comp;j++){
for(auto it : cicles[j]){
if(it >= cicles[i][0] && it <= cicles[i].back()){
mini = min(mini, cicles[j][0]);
maxi = max(maxi, cicles[j].back());
}
}
}
extend[i].fr = mini;
extend[i].sc = maxi;
}
while(p[l_ned] == l_ned && s > l_ned) l_ned++;
r_ned = n - 1;
while(p[r_ned] == r_ned && s < r_ned) r_ned--;
return compute(extend[viz[s]].fr, extend[viz[s]].sc) + ans;
}
