#include "books.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int nx=1e6+5;
int n, vs[nx], qs[nx], offl[nx], offr[nx], mn[nx], mx[nx], cl, cr, L, R;
ll res;
void updaterange()
{
for (int i=cl; i<=cr; i++)
{
if (mn[i]<cl) return cl=mn[i], updaterange();
if (mx[i]>cr) return cr=mx[i], updaterange();
}
}
long long minimum_walk(std::vector<int> p, int s) {
n=p.size();
for (int i=0; i<n; i++)
{
res+=abs(i-p[i]);
if (vs[i]) continue;
int cmn=i, cmx=i, u=i;
vs[i]=1;
vector<int> pass={u};
while (p[u]!=i) u=p[u], vs[u]=1, cmx=max(cmx, u), pass.push_back(u);
qs[cmn]++, qs[cmx]--;
for (auto u:pass) mn[u]=cmn, mx[u]=cmx;
}
for (int i=0; i<n; i++) offl[i]=offr[i]=(mn[i]==mx[i]);
for (int i=n-2; i>=0; i--) offr[i]=offr[i]&&offr[i+1];
for (int i=1; i<n; i++) offl[i]=offl[i]&&offl[i-1];
for (int i=1; i<n; i++) qs[i]+=qs[i-1];
for (int i=0; i<s; i++) if (qs[i]==0&&!offl[i]) res+=2;
for (int i=s; i<n-1; i++) if (qs[i]==0&&!offr[i+1]) res+=2;
L=R=cl=cr=s;
while (L>0&&qs[L-1]) L--;
while (R<n-1&&qs[R]) R++;
while (cl!=L||cr!=R)
{
updaterange();
// cout<<"debug "<<cl<<' '<<cr<<'\n';
int movel=cl, mover=cr, cstl=0, cstr=0;
while (movel>L)
{
movel--;
cstl++;
bool ed=0;
movel=mn[movel];
for (int i=mn[movel]; i<=mx[movel]; i++) if (mx[i]>cr) ed=1;
if (ed) break;
}
while (mover<R)
{
mover++;
cstr++;
bool ed=0;
mover=mx[mover];
for (int i=mn[mover]; i<=mx[mover]; i++) if (mn[i]<cl) ed=1;
if (ed) break;
}
// cout<<"here "<<cl<<' '<<cr<<' '<<movel<<' '<<mover<<'\n';
res+=2*min(cstl, cstr);
cl=movel, cr=mover;
}
return res;
}
/*
7 3
0 5 2 3 4 1 6
*/
