//#pragma once
//#include "grader.cpp"
#include "books.h"
#include <bits/stdc++.h>
using namespace std;
struct cell
{
int l,r;
long long int st;
};
bool cmp(cell a1,cell a2)
{
return a1.l<a2.l;
}
int n,s,br,mid,used[1000005],a[1000005],ind[1000005],f1,f2;
long long int otg=0;
cell p[1000005];
void dfs(int beg)
{
p[br].l=min(p[br].l,beg);
p[br].r=max(p[br].r,beg);
p[br].st+=abs(a[beg]-beg);
ind[beg]=br;
used[beg]=1;
if(!used[a[beg]])
{
dfs(a[beg]);
}
}
void prec()
{
for(int i=1; i<=n; i++)
{
if(!used[i])
{
br++;
p[br].l=1e9;
dfs(i);
otg+=p[br].st;
}
}
memset(used,0,sizeof(used));
sort(p+1,p+br+1,cmp);
for(int i=1;i<=n;i++)
{
if(a[i]!=i)
{
f1=i;
break;
}
}
for(int i=n;i>=1;i--)
{
if(a[i]!=i)
{
f2=i;
break;
}
}
}
void resh()
{
int tol=s,tor=s+1,l=s,r=s,i1,i2;
long long int dobl=0,dobr=0,dob=0,br=0;
while(true)
{
if(tol==0&&tor==n+1)break;
i1=ind[tol];
i2=ind[tor];
//cout<<i1<<" "<<i2<<" "<<tol<<" "<<tor<<endl;
br++;
if(br==1000000)return;
if(used[i1])
{
tol--;
continue;
}
if(used[i2])
{
tor++;
continue;
}
if(tol>0&&p[i1].r<=s)
{
if(p[i1].l!=p[i1].r)
{
if(l>tol)dobl+=l-tol;
l=min(l,p[i1].l);
}
used[i1]=1;
tol--;
}
if(tor<n+1&&p[i2].l>s)
{
if(p[i2].l!=p[i2].r)
{
if(r<tor)dobr+=tor-r;
r=max(r,p[i2].r);
}
used[i2]=1;
tor++;
}
if(i1==i2)
{
if(l>tol)dobl+=l-tol;
if(r<tor)dobr+=tor-r;
dob+=min(dobl,dobr);
dobl=0;
dobr=0;
l=min(l,p[i1].l);
r=max(r,p[i2].r);
used[i1]=1;
tol--;
tor++;
}
}
otg+=(dobl+dobr+dob)*2;
}
long long minimum_walk(std::vector<int> p, int S)
{
n=p.size();
s=S+1;
for(int i=1; i<=n; i++)
{
a[i]=p[i-1]+1;
}
prec();
resh();
return otg;
}
