#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;
struct segtreemax
{
int d[4*nx];
void build(int l, int r, int i)
{
if (l==r) return d[i]=mx[l], void();
int md=(l+r)/2;
build(l, md, 2*i);
build(md+1, r, 2*i+1);
d[i]=max(d[2*i], d[2*i+1]);
}
int query(int l, int r, int i, int ql, int qr)
{
if (qr<l||r<ql) return 0;
if (ql<=l&&r<=qr) return d[i];
int md=(l+r)/2;
return max(query(l, md, 2*i, ql, qr), query(md+1, r, 2*i+1, ql, qr));
}
} smx;
struct segtreemin
{
int d[4*nx];
void build(int l, int r, int i)
{
if (l==r) return d[i]=mn[l], void();
int md=(l+r)/2;
build(l, md, 2*i);
build(md+1, r, 2*i+1);
d[i]=min(d[2*i], d[2*i+1]);
}
int query(int l, int r, int i, int ql, int qr)
{
if (qr<l||r<ql) return 1e9;
if (ql<=l&&r<=qr) return d[i];
int md=(l+r)/2;
return min(query(l, md, 2*i, ql, qr), query(md+1, r, 2*i+1, ql, qr));
}
} smn;
void updaterange()
{
int nmn=smn.query(1, n, 1, cl, cr);
if (nmn<cl) return cl=nmn, updaterange();
int nmx=smx.query(1, n, 1, cl, cr);
if (nmx>cr) return cr=nmx, 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;
smx.build(1, n, 1);
smn.build(1, n, 1);
L=R=cl=cr=s;
while (L>0&&qs[L-1]) L--;
while (R<n-1&&qs[R]) R++;
updaterange();
while (cl!=L||cr!=R)
{
// 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];
while (1)
{
if (smx.query(1, n, 1, mn[movel], mx[movel])>cr)
{
ed=1;
break;
}
if (smn.query(1, n, 1, mn[movel], mx[movel])>=movel) break;
movel=smn.query(1, n, 1, mn[movel], mx[movel]);
}
if (ed) break;
}
while (mover<R)
{
mover++;
cstr++;
bool ed=0;
mover=mx[mover];
while (1)
{
if (smn.query(1, n, 1, mn[mover], mx[mover])<cl)
{
ed=1;
break;
}
if (smx.query(1,n , 1, mn[mover], mx[mover])<=mover) break;
mover=smx.query(1,n , 1, mn[mover], mx[mover]);
}
if (ed) break;
}
// cout<<"here "<<cl<<' '<<cr<<' '<<movel<<' '<<mover<<'\n';
res+=2*min(cstl, cstr);
cl=movel, cr=mover;
updaterange();
}
return res;
}
/*
7 3
0 5 2 3 4 1 6
*/
