#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vll vector<ll>
#define all(x) begin(x),end(x)
#define pb push_back
const int N=1e6+10;
bool vis[N];
pair<int,int> range[N];
void maximize_range(pair<int,int>& a,pair<int,int>&b)
{
a.first=min(a.first,b.first);
a.second=max(a.second,b.second);
}
void extend(pair<int,int>& a,pair<int,int>& b)
{
while(b.first<a.first or a.second<b.second)
{
if(b.first<a.first)
{
maximize_range(b,range[--a.first]);
}
else
{
maximize_range(b,range[++a.second]);
}
}
}
long long minimum_walk(std::vector<int> p, int s)
{
int cyc=0;
int n=p.size();
ll ans=0;
for(int i=0;i<n;i++)ans+=abs(p[i]-i);
pair<int,int> want={s,s};
for(int i=0;i<n;i++)
{
if(vis[i])continue;
int j=i;
range[i]={i,i};
if(p[i]!=i)
{
maximize_range(want,range[i]);
}
while(!vis[j])
{
vis[j]=1;
j=p[j];
range[i].first=min(range[i].first,j);
range[i].second=max(range[i].second,j);
}
do{
range[j]=range[i];
j=p[j];
}while(j!=i);
// cyc++;
}
pair<int,int> cur={s,s};
pair<int,int> full=range[s];
while(true)
{
extend(cur,full);
if(cur.first<=want.first and want.second<=cur.second)break; // we contained all non trivial cycles
int left=0,right=0;
bool same=1;
auto cur_=cur,full_=full;
while(want.first<cur_.first and cur_.second==full.second)
{
maximize_range(full_,range[--cur_.first]);
left++;
extend(cur_,full_);
}
if(cur_.second==full.second)same=0;
cur_=cur,full_=full;
while(want.second>cur_.second and cur_.first==full.first)
{
maximize_range(full_,range[++cur_.second]);
right++;
extend(cur_,full_);
}
if(cur_.first==full.first)same=0;
if(same)
{
ans+=min(left,right)*2;
cur=cur_;
full=full_;
}
else{
ans+=(left+right)*2;
break;
}
}
return ans;
}
