#include "books.h"
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define x first
#define y second
int f[1000005];
int l[1000005];
int r[1000005];
int Find(int x){
if(f[x]==x)return x;
return f[x]=Find(f[x]);
}
int pre[1000005];
vector<pii> edge[4000005];
int dis[4000005];
int ok[1000005];
int vis[4000005];
int mindex;
struct node{
node *l,*r;
//list<int> v;
int num;
int a,b;
node(int _a,int _b):a(_a),b(_b),l(NULL),r(NULL){
num=mindex++;
}
}*root;
void build(node *n){
if(n->a==n->b){
edge[n->num].pb(mp(n->a,0));
return;
}
int mid=(n->a+n->b)/2;
n->l=new node(n->a,mid);
n->r=new node(mid+1,n->b);
edge[n->num].push_back(mp(n->l->num,0));
edge[n->num].push_back(mp(n->r->num,0));
build(n->l);
build(n->r);
}
void go(node *n,int l,int r,int x){
if(n->a>=l&&n->b<=r){
edge[x].push_back(mp(n->num,0));
return ;
}
if(n->b<l||n->a>r)return;
go(n->l,l,r,x);
go(n->r,l,r,x);
}
long long minimum_walk(std::vector<int> p, int s) {
// vector<pii> v;
mindex=p.size();
long long ans=0;
int Min=1e9;
int over=0;
for(int i = 0;i<p.size();i++){
if(p[i]!=i){
// v.pb(mp(p[i],i));
ans+=abs(p[i]-i);
// Min=min(Min,abs(i-s));
if((i<s&&p[i]>s)||(i>s&&p[i]<s))over=1;
}
l[i]=1e9;
r[i]=0;
f[i]=i;
}
for(int i = 0;i<p.size();i++){
f[Find(p[i])]=Find(i);
}
for(int i = 0;i<p.size();i++){
l[Find(i)]=min(l[Find(i)],i);
r[Find(i)]=max(r[Find(i)],i);
}
vector<pii> v;
root = new node(0,p.size()-1);
build(root);
for(int i = 0;i<p.size();i++){
if(f[i]==i&&l[i]!=r[i]){
v.pb(mp(l[i],r[i]));
}
}
if(v.empty())return 0;
sort(v.begin(),v.end());
int Max=v[0].y;
ok[v[0].x]=1;
for(auto it:v){
if(Max<it.x){
ok[Max]=1;
ok[it.x]=1;
}
ans+=max(0,(it.x-Max)*2);
Max=max(Max,it.y);
}
ok[Max]=1;
if(!over){
// printf("?\n");
if(s>Max||s<v[0].x){
Min=max(s-Max,v[0].x-s);
}
else{
//printf("%d ?\n",ans);
Min=0;
}
}
else{
for(int i = 0;i<p.size();i++){
if(p[i]<i){
go(root,p[i],i,i);
}
if(p[i]>i){
go(root,i,p[i],i);
}
if(i!=0){
edge[i].pb(mp(i-1,1));
}
if(i!=p.size()){
edge[i].pb(mp(i+1,1));
}
}
vector<int> q,q2;
q.pb(s);
fill(dis,dis+mindex,1e9);
dis[s]=0;
fill(vis,vis+mindex,0);
while(!q.empty()){
for(int i = 0;i<q.size();i++){
int x=q[i];
if(vis[x])continue;
vis[x]=1;
// printf("%d %d\n",x,dis[x]);
for(auto it:edge[x]){
if(it.y==0){
if(dis[it.x]>dis[x]){
dis[it.x]=dis[x];
// printf("go %d %d\n",it.x,dis[it.x]);
q.pb(it.x);
}
}
else{
if(dis[it.x]>dis[x]+1){
dis[it.x]=dis[x]+1;
// printf("go2 %d %d\n",it.x,dis[it.x]);
q2.pb(it.x);
}
}
}
}
swap(q,q2);
q2.clear();
}
/*
while(!q.empty()){
int x=q.front();
q.pop_front();
if(vis[x])continue;
vis[x]=1;
for(auto it:edge[x]){
}
}
}*/
for(int i = 0;i<p.size();i++){
if(ok[i]){
Min=min(Min,dis[i]);
}
}
}
// printf("%d\n",Min);
return ans+Min*2;
}
/*
8
7 3 4 1 2 5 6 0
*/
