#include <bits/stdc++.h>
#include "books.h"
using namespace std;
const long long inf=1e18;
long long n,a[1000069],fh[2][1000069],nr[1000069],dsu[1000069];
bitset<1000069> vtd,vtd2;
queue<long long> q;
long long fd(long long x)
{
if(dsu[x]!=x)
{
dsu[x]=fd(dsu[x]);
}
return dsu[x];
}
void ad(long long x,long long w)
{
long long i,p,sz;
vector<long long> v;
for(p=fh[0][x];fd(p)<=fh[1][x];dsu[fd(p)]=fd(fd(p)+1))
{
q.push(fd(p));
nr[fd(p)]=w;
v.push_back(fd(p));
}
sz=v.size();
for(i=0;i<sz;i++)
{
ad(v[i],w);
}
}
long long minimum_walk(vector<int> aa,int st)
{
long long i,ii,u,k,p,mn,mx,z=0;
st++;
n=aa.size();
for(i=1;i<=n;i++)
{
a[i]=aa[i-1]+1;
z+=abs(i-a[i]);
nr[i]=inf;
}
for(i=1;i<=n;i++)
{
if(!vtd[i])
{
mn=i;
mx=i;
for(p=i;!vtd[p];p=a[p])
{
vtd[p]=1;
mn=min(mn,p);
mx=max(mx,p);
}
for(p=i;!vtd2[p];p=a[p])
{
vtd2[p]=1;
fh[0][p]=mn;
fh[1][p]=mx;
}
}
}
for(i=1;i<=n+1;i++)
{
dsu[i]=i;
}
ad(st,0);
mx=0;
for(;!q.empty();)
{
k=q.front();
q.pop();
if(fh[0][k]<=st&&fh[1][k]>=st)
{
mx=nr[k];
}
for(ii=0;ii<2;ii++)
{
u=!ii*2-1;
if(k+u&&k+u<=n)
{
ad(k+u,nr[k]+1);
}
}
}
z+=mx*2;
mn=st;
mx=st;
for(i=1;i<=n;i++)
{
if(a[i]!=i)
{
mn=min(mn,i);
mx=max(mx,i);
}
}
k=0;
for(i=mn;i<mx;i++)
{
k=max(k,fh[1][i]);
z+=2*(k==i);
}
return z;
}
