#include "books.h"
#include "bits/stdc++.h"
using namespace std;
#ifndef EVAL
#include "grader.cpp"
#endif
#define ll long long
#define sz(x) (int)x.size()
#define pb push_back
#define pii pair<int, int>
#define ff first
#define ss second
const ll inf = 1e9+7;
const int N = 1e6+5;
const int mod = 1e9+7;
int n, used[N], last, L[N], R[N], in[N];
int endL, endR;
map<pii, ll> dp;
void ext(int &l, int &r){
int new_l = min(L[in[l]], L[in[r]]), new_r = max(R[in[r]], R[in[l]]);
while(1){
if(new_l < l) new_l = min(L[in[--l]], new_l), new_r = max(R[in[l]], new_r);
else if(new_r > r) new_l = min(L[in[++r]], new_l), new_r = max(R[in[r]], new_r);
else break;
}//return {new_l, new_r};
}
ll fun(int l, int r){
ext(l, r);
if(l == endL && r == endR) return 0;
if(dp.find(make_pair(l, r)) != dp.end()) return dp[make_pair(l, r)];
if(l == endL) return dp[{l, r}] = fun(l, r+1)+2;
if(r == endL) return dp[{l, r}] = fun(l-1, r)+2;
int l_l = l-1, l_r = r; ext(l_l, l_r);
int r_l = l, r_r = r+1; ext(r_l, r_r);
int lans = 1, rans = 1;
// trying to move our tmpl while our tmpr is < our extended {l, r+1} range
while(l_l != endL && l_r < r_r){
lans++, l_l--;
ext(l_l, l_r);
}if(l_r < r_r) return dp[{l, r}] = lans*2 + fun(l_l, l_r);
// trying to move our tmpr while our tmpl is > our extended {l-1, r} range
r_r = r+1, r_l = l; ext(r_l, r_r);
l_l = l-1, l_r = r; ext(l_l, l_r);
while(r_r != endR && r_l > l_l){
rans++, r_r++;
ext(r_l, r_r);
}if(r_l > l_l) return dp[{l, r}] = rans*2 + fun(r_l, r_r);
return dp[{l, r}] = min(lans, rans)*2 + fun(r_l, r_r);
}
ll minimum_walk(vector<int> p, int s) {
//memset(dp, -1, sizeof dp);
ll res = 0;
endL = s, endR = s, n = sz(p);
for(int i=0;i<n;i++){
if(!used[i]){
int u = i;
L[last] = u, R[last] = u;
do{
used[u] = 1;
in[u] = last;
L[last] = min(L[last], u);
R[last] = max(R[last], u);
res += abs(p[u] - u);
u = p[u];
}while(u != i);
if(L[last] != R[last]){
endL = min(L[last], endL);
endR = max(R[last], endR);
}
last++;
}
}
return fun(s, s) + res;
}
