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