#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MN = 1e6+6;
ll n, s, x, id[MN], l[MN], r[MN], a[MN], b[MN], aa[MN], bb[MN], nxt, ans, arr[MN], i, j, par[MN], dist[MN], L=1<<30, R, vs[MN];
vector<int> adj[MN], rev[MN];
deque<int> q;
void dfs(ll n){
ans += abs(arr[n]-n);
a[id[n]]=min(a[id[n]],n);
b[id[n]]=max(b[id[n]],n);
if(n<=s) aa[id[n]]=max(aa[id[n]],n);
if(n>=s) bb[id[n]]=min(bb[id[n]],n);
if(id[arr[n]]) return;
id[arr[n]]=id[n];
dfs(arr[n]);
}
ll minimum_walk(vector<int> p,int e){
n = p.size(); s = e+1;
for(i=0;i<n;i++) arr[i+1]=p[i]+1;
for(i=1;i<=n;i++){
a[i] = bb[i] = 1<<30;
if(!id[i]){
id[i] = ++nxt;
dfs(i);
}
}
for(i=1;i<=nxt;i++){
if(a[i]==b[i]) continue;
L = min(L, a[i]);
R = max(R, b[i]);
if(a[i]<=s&&s<=b[i]){
l[a[i]]++; l[b[i]]--;
l[aa[i]]--; l[s]++;
r[b[i]]++; r[a[i]]--;
r[s]++; r[bb[i]]--;
adj[aa[i]].push_back(bb[i]);
adj[bb[i]].push_back(aa[i]);
}
else{
l[a[i]]++; l[b[i]]--;
r[b[i]]++; r[a[i]]--;
}
}
if(R==0) return 0LL;
for(i=1;i<=n;i++){
x += l[i];
if(x) adj[i+1].push_back(i);
}
x = 0;
for(i=n;i>=1;i--){
x += r[i];
if(x) adj[i-1].push_back(i);
}
memset(dist,-1,sizeof(dist));
q.push_back(s); dist[s] = 0;
while(q.size()){
x = q.front(); q.pop_front();
if(vs[x]) continue;
vs[x] = 1;
for(auto v : adj[x]){
if(dist[v]==-1||dist[x]<dist[v]){
dist[v] = dist[x]; par[v] = x;
q.push_front(v);
}
}
if(x>1&&dist[x-1]==-1){
dist[x-1] = dist[x]+1; par[x-1] = x;
q.push_back(x-1);
}
if(x<n&&dist[x+1]==-1){
dist[x+1] = dist[x]+1; par[x+1] = x;
q.push_back(x+1);
}
}
ans += 2*dist[L];
memset(dist,-1,sizeof(dist));
memset(vs,0,sizeof(vs));
x = L;
while(1){
q.push_back(x);
dist[x] = 0;
if(!par[x]) break;
x = par[x];
}
while(q.size()){
x = q.front(); q.pop_front();
if(vs[x]) continue;
vs[x] = 1;
for(auto v : adj[x]){
if(dist[v]==-1||dist[x]<dist[v]){
dist[v] = dist[x]; par[v] = x;
q.push_front(v);
}
}
if(x>1&&dist[x-1]==-1){
dist[x-1] = dist[x]+1; par[x-1] = x;
q.push_back(x-1);
}
if(x<n&&dist[x+1]==-1){
dist[x+1] = dist[x]+1; par[x+1] = x;
q.push_back(x+1);
}
}
ans += 2*dist[R];
return ans;
}
