#include <bits/stdc++.h>
using namespace std;
const int MN = 1e6+6;
typedef long long ll;
ll n, m, s, i, j, l[MN], r[MN], id[MN], arr[MN], vis[MN], vs[MN], ac[MN], nxt, ans, L, R, _l[MN], _r[MN];
vector<int> res, ress; set<int> avail;
void dfs(ll n){
ans += abs(n-arr[n]);
l[id[n]]=min(l[id[n]],n);
r[id[n]]=max(r[id[n]],n);
if(id[arr[n]]) return;
id[arr[n]]=id[n];
dfs(arr[n]);
}
void ddfs(ll n,ll p=0){
if(vs[n]) return;
res.push_back(n); vs[n]=1;
vector<int> to;
auto it = avail.lower_bound(l[n]);
while(it!=avail.end()&&*it<=r[n]){
int v = *it; ress.push_back(v);
auto it2 = it; it++;
avail.erase(it2);
if(!vs[id[v]]) to.push_back(id[v]);
}
for(auto v : to) ddfs(v, p);
if(p) L=min(L,l[n]), R=max(R,r[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++){
avail.insert(i);
l[i] = 1<<30;
if(!id[i]){
id[i] = ++nxt;
dfs(i);
}
}
for(i=1;i<=nxt;i++){
if(l[i]!=r[i]) ac[++m]=i;
}
L = R = s;
while(1){
ll LL, RR;
for(i=_r[R];i+R<=n&&(arr[i+R]==i+R||vs[id[i+R]]);i++){}
RR = i+R; _r[R] = i;
for(i=_l[L];L-i>=1&&(arr[L-i]==L-i||vs[id[L-i]]);i++){}
LL = L-i; _l[L] = i;
if(RR<=n&&LL>=1){
int wth = 0;
if(abs(RR-R)>abs(LL-L)) swap(LL,RR), wth=1;
ddfs(id[RR]);
if(vs[id[LL]]){
if(!wth) ans += 2*abs(RR-R);
else ans += 2*abs(RR-L);
for(auto v : res) vs[v]=0;
for(auto v : ress) avail.insert(v);
res.clear(); ress.clear();
ddfs(id[RR],1);
res.clear(); ress.clear();
continue;
}
for(auto v : res) vs[v]=0;
for(auto v : ress) avail.insert(v);
res.clear(); ress.clear();
if(!wth) ans += 2*abs(L-LL);
else ans += 2*abs(R-LL);
ddfs(id[LL],1);
res.clear(); ress.clear();
}
else if(RR<=n){
ans += 2*(RR-R);
ddfs(id[RR], 1);
res.clear(); ress.clear();
}
else if(LL>=1){
ans += 2*(L-LL);
ddfs(id[LL], 1);
res.clear(); ress.clear();
}
else break;
}
return ans;
}
