#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];
int num[N],L[N],R[N],d[N];
void add(int l,int r)
{
d[l]++;
d[r+1]--;
}
long long minimum_walk(std::vector<int> p, int s)
{
int cyc=0;
int n=p.size();
for(int i=0;i<=n;i++)vis[i]=0,L[i]=R[i]=-2e9,d[i]=0;
ll ans=0;
for(int i=0;i<n;i++)ans+=abs(p[i]-i);
for(int i=0;i<n;i++)
{
if(i!=p[i])
add(min(i,p[i])+1,max(i,p[i]));
if(vis[i] or p[i]==i)continue;
int j=i;
L[cyc]=R[cyc]=i;
while(!vis[j])
{
num[j]=cyc;
vis[j]=1;
j=p[j];
R[cyc]=max(R[cyc],j);
}
cyc++;
}
set<int> tp;
int r=n-1;
while(r>=0 and p[r]==r){r--;}
for(int i=0;i<r;i++)
{
d[i+1]+=d[i];
if(i!=p[i])
tp.insert(num[i]);
if(tp.size()!=cyc and d[i+1]==0)
{
ans+=2;
}
}
return ans;
}
// int main()
// {
// int n,s;
// cin>>n>>s;
// vector<int> p(n);
// for(int i=0;i<n;i++)cin>>p[i];
// cout<<minimum_walk(p,s)<<endl;
// }
