#include <bits/stdc++.h>
#define ll long long
#define db long double
#define N 1000005
#define II pair <ll,ll>
#define III pair <ll,II>
#define IV pair <vector <int>,vector <int> >
#define IDB pair <db,int>
#define TII pair <treap*,treap*>
#define fst first
#define snd second
#define BIT(x,i) ((x>>i)&1)
#define pi acos(-1)
#define to_radian(x) (x*pi/180.0)
#define to_degree(x) (x*180.0/pi)
#define Log(x) (31-__builtin_clz((int)x))
#define LogLL(x) (63-__builtin_clzll((ll)x)
using namespace std;
#include "books.h"
struct Minimum_Fenwick_Tree
{
int bit[N],d[N];
void Init()
{
memset(bit,63,sizeof(bit));
memset(d,63,sizeof(d));
}
void update(int i,int k)
{
d[i]=min(d[i],k);
while(i<N) bit[i]=min(bit[i],k),i+=(i & -i);
}
int get(int l,int r)
{
int res=1e9,i=r;
while(i>=l)
if(i-(i & -i)>=l) res=min(res,bit[i]),i-=(i & -i);
else res=min(res,d[i]),i--;
return res;
}
} FT_mi;
struct Maximum_Fenwick_Tree
{
int bit[N],d[N];
void update(int i,int k)
{
d[i]=max(d[i],k);
while(i<N) bit[i]=max(bit[i],k),i+=(i & -i);
}
int get(int l,int r)
{
int res=0,i=r;
while(i>=l)
if(i-(i & -i)>=l) res=max(res,bit[i]),i-=(i & -i);
else res=max(res,d[i]),i--;
return res;
}
} FT_ma,FT_done;
int n,i,j,k,pos,p[N],n_cycle,n_node,n_point,in[N],par[N];
vector <int> a[N],Set[N];
II seg_node[N],seg_cycle[N],point[2*N];
ll minimum_walk(vector <int> _p,int s)
{
s++;
for(int k:_p) p[++n]=k,p[n]++;
//Build cycle
for(i=1;i<=n;i++)
if(in[i]==0)
{
n_cycle++;
int l=1e9,r=0;
for(j=i;in[j]==0;j=p[j])
{
l=min(l,j);
r=max(r,j);
in[j]=n_cycle;
Set[n_cycle].push_back(j);
}
// if(l==2 && r==2) cerr<<p[i]<<'\n';
seg_cycle[n_cycle]={ l,r };
}
sort(seg_cycle+1,seg_cycle+n_cycle+1,[&](II a,II b){ return a.snd<b.snd; });
//Build extend segment
FT_mi.Init();
set <II> vec;
for(i=1;i<=n_cycle;i++)
{
int l=seg_cycle[i].fst,r=seg_cycle[i].snd,x=in[l];
// if(l==8 && r==839) cerr<<1<<'\n';
// cerr<<l<<" "<<r<<'\n';
// if(FT_ma.get(1,l)>=r) continue;
// if(l<=s && s<=r) cerr<<l<<" "<<r<<'\n';
while(1)
{
int k;
if((k=FT_mi.get(l,r))<l) l=k;
else if((k=FT_ma.get(l,r))>r) r=k;
else break;
}
// FT_done.update(l,r);
for(int k:Set[x])
{
FT_mi.update(k,l);
FT_ma.update(k,r);
}
vec.insert({ l,r });
}
// cerr<<in[8]<<" "<<in[839]<<'\n';
for(II k:vec)
{
int l=k.fst,r=k.snd;
if(FT_mi.get(l,r)>=l && FT_ma.get(l,r)<=r)
{
// cout<<l<<" "<<r<<'\n';
point[++n_point]={ l,0 };
point[++n_point]={ r,1 };
}
}
// cerr<<n_point<<'\n';
sort(point+1,point+n_point+1);
//Build Tree of extend segment
stack <II> st;
for(i=1;i<=n_point;i++)
if(point[i].snd==0) st.push(point[i]);
else
{
n_node++;
while(st.top().snd==1)
{
int u=st.top().fst;
a[n_node].push_back(u);
par[u]=n_node;
st.pop();
}
seg_node[n_node]={ st.top().fst,point[i].fst };
reverse(a[n_node].begin(),a[n_node].end());
st.pop();
st.push({ n_node,1 });
}
//Init move
int Begin=0,End=0;
ll res=0;
for(i=1;i<=n;i++)
{
res+=abs(i-p[i]);
if(i!=p[i])
{
if(Begin==0) Begin=i;
End=i;
}
}
if(Begin==0) return 0;
Begin=min(Begin,s);
End=max(End,s);
for(i=1;i<=n_node;i++)
{
if(seg_node[i].fst>=Begin && seg_node[i].snd<=End && par[i]==0)
res+=2;
}
res-=2;
int mn_len=1e9;
for(i=1;i<=n_node;i++)
if(seg_node[i].fst<=s && s<=seg_node[i].snd && mn_len>seg_node[i].snd-seg_node[i].fst)
{
mn_len=seg_node[i].snd-seg_node[i].fst;
pos=i;
}
i=pos;
// cerr<<seg_node[i].fst<<" "<<seg_node[i].snd<<" "<<p[401]<<'\n';
while(par[i]>0)
{
j=par[i];//cerr<<seg_node[i].fst<<" "<<seg_node[i].snd<<'\n';
ll cl=0,cr=0;
for(pos=0;pos<a[j].size();pos++)
if(a[j][pos]==i) break;
for(k=pos;k>=0;k--)
{
cl++;
if(k>0 && seg_node[a[j][k]].fst-seg_node[a[j][k-1]].snd>1) break;
}
for(k=pos;k<a[j].size();k++)
{
cr++;
if(k<a[j].size()-1 && seg_node[a[j][k+1]].fst-seg_node[a[j][k]].snd>1) break;
}
res+=2*min(cl,cr);
i=j;
}
return res;
}
/*
int main()
{
freopen("books.inp","r",stdin);
freopen("books.out","w",stdout);
vector <int> p;
int n,s,k;
cin>>n>>s;
for(int i=1;i<=n;i++) cin>>k,p.push_back(k);
cout<<minimum_walk(p,s);
}
*/
