#include "books.h"
#include<bits/stdc++.h>
using namespace std;
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ll long long
#define ordered_set tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>
#define fall(i,a,b) for(int i=a;i<=b;i++)
#define rfall(i,a,b) for(int i=a;i>=b;i--)
#define pb push_back
#define all(x) x.begin(),x.end()
#define sz(x) (int)x.size()
const ll inf=1e17;
long long minimum_walk(std::vector<int> p, int s){
int n=sz(p);
int lef,ri,r=-1;
fall(i,0,n-1){
r=i;
int j=i;
while(j<=r){
r=max(r,p[j]); j++;
}
if(i<=s && r>=s) lef=i,ri=r;
i=r;
}
ll ans=0;
fall(i,0,n-1) ans+=abs(i-p[i]);
int ad=1,l=lef;
rfall(i,lef-1,0){
int j=i;
l=i;
while(j>=l){
l=min(l,p[j]); j--;
}
if(l==i){
ad+=2;
continue;
}
ans+=ad; ad=0;
ad++; ans++;
i=l;
}
ad=1;
r=ri;
fall(i,ri+1,n-1){
r=i;
int j=i;
while(j<=r){
r=max(r,p[j]);
j++;
}
if(r==i){
ad+=2;
continue;
}
ans+=ad; ad=0;
ad++; ans++;
i=r;
}
vector<int> pai(n,-1),dp(n,n+10),mx(n);
vector<vector<int>> g(n),comp(n);
fall(i,lef,ri){
if(pai[i]!=-1) continue;
int x=i;
while(pai[x]==-1){
pai[x]=i;
comp[i].pb(x);
mx[i]=max(mx[i],x);
x=p[x];
}
}
fall(i,lef,ri-1) g[pai[i]].pb(pai[i+1]),g[pai[i+1]].pb(pai[i]);
deque<int> dq; dq.pb(pai[s]); dp[pai[s]]=0;
set<int> st;
fall(i,lef,ri) st.insert(i);
while(!dq.empty()){
auto x=dq.front(); dq.pop_front();
while(true){
auto it=st.lower_bound(x);
if(it==st.end() || *it>mx[x]) break;
int i=*it;
int j=pai[i];
if(dp[j]>dp[x]){
dp[j]=dp[x];
dq.push_front(j);
}
st.erase(it);
}
for(auto u:g[x]){
if(dp[u]>dp[x]+1){
dp[u]=dp[x]+1;
dq.pb(u);
}
}
}
ans+=2*dp[lef];
return ans;
}
