#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; // }