#include "books.h"
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define rng(i,l,r) for(int i=(l); i<(r); i++)
#define all(x) x.begin(),x.end()
using ll=long long;
const int INF=INT_MAX>>1;
struct SegTree{
using T=pair<int,int>;
inline T op(T x,T y){
return {min(x.first,y.first),max(x.second,y.second)};
}
inline T e(){
return {INF,-INF};
}
vector<T> tree;
int size;
SegTree(int sz):size(sz){
tree.resize(size*2,e());
}
inline T get(int pos){
return tree[pos+size];
}
inline void set(int pos,T val){
pos+=size;
tree[pos]=val;
pos>>=1;
while(pos>=1){
tree[pos]=op(tree[pos*2],tree[pos*2+1]);
pos>>=1;
}
}
T prod(int lf,int ri){
lf+=size;
ri+=size;
T rl=e();
T rr=e();
while(lf<ri){
if(lf&1){
rl=op(rl,tree[lf]);
lf++;
}
if(ri&1){
ri--;
rr=op(tree[ri],rr);
}
lf>>=1;
ri>>=1;
}
return op(rl,rr);
}
};
long long minimum_walk(std::vector<int> p, int s) {
int n=p.size();
vector<int> vis(n,-1);
vector<pair<int,int>> wide;
int cnt=0;
ll ans=0;
rep(i,n){
if(vis[i]>=0)continue;
if(p[i]==i&&i!=s)continue;
int lf=i;
int ri=i;
int pos=i;
while(vis[p[pos]]==-1){
ans+=abs(pos-p[pos]);
pos=p[pos];
vis[pos]=cnt;
lf=min(lf,pos);
ri=max(ri,pos);
}
cnt++;
wide.emplace_back(lf,ri);
}
int sl,sr;
{
vector<pair<int,int>> seg=wide;
sort(all(seg));
vector<pair<int,int>> re={seg[0]};
rng(i,1,seg.size()){
if(seg[i].first<=re.back().second){
re.back().second=max(re.back().second,seg[i].second);
}
else{
re.emplace_back(seg[i]);
}
}
rep(i,re.size()-1){
ans+=2*(re[i+1].first-re[i].second);
}
for(auto i:re){
if(i.first<=s&&s<=i.second){
sl=i.first;
sr=i.second;
break;
}
}
}
vector<int> dist(cnt,INF);
dist[vis[s]]=0;
SegTree seg(n);
rng(i,sl,sr+1){
if(vis[i]!=-1){
seg.set(i,{i,i});
}
}
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
pq.push({0,vis[s]});
while(!pq.empty()){
int dis,pos;
tie(dis,pos)=pq.top();
pq.pop();
if(dist[pos]!=dis)continue;
int lf,ri;
tie(lf,ri)=wide[pos];
while(true){
int nxt=seg.prod(lf+1,ri).first;
if(nxt>n)break;
seg.set(nxt,seg.e());
if(dist[vis[nxt]]>dis){
dist[vis[nxt]]=dis;
pq.push({dist[vis[nxt]],vis[nxt]});
}
}
int nxt;
nxt=seg.prod(0,lf).second;
if(0<=nxt){
if(dist[vis[nxt]]>dis+abs(nxt-lf)){
dist[vis[nxt]]=dis+abs(nxt-lf);
pq.push({dist[vis[nxt]],vis[nxt]});
}
}
nxt=seg.prod(ri+1,n).first;
if(nxt<n){
if(dist[vis[nxt]]>dis+abs(nxt-ri)){
dist[vis[nxt]]=dis+abs(nxt-ri);
pq.push({dist[vis[nxt]],vis[nxt]});
}
}
}
rep(i,cnt){
if(wide[i].first==sl){
ans+=dist[i]*2;
break;
}
}
return ans;
}
