#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], oncy[nx], havecy, d[nx];
ll res;
vector<pair<int, int>> rng;
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 mn=i, mx=i, u=i;
vs[i]=1;
oncy[i]=1;
while (p[u]!=i) u=p[u], vs[u]=1, mx=max(mx, u), oncy[u]=1;
qs[mn]++, qs[mx]--;
if (mn==mx) offl[i]=offr[i]=1, oncy[i]=0;
else havecy=1;
// cout<<"debug "<<i<<' '<<mn<<' '<<mx<<'\n';
rng.push_back({mn, mx});
}
if (!havecy) return 0ll;
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;
if (!oncy[s]&&qs[s])
{
int cst=INT_MAX;
for (auto [l, r]:rng)
{
int cnt1=0, cnt2=0;
if (l<s&&s<r)
{
for (int i=l; i<r; i++) qs[i]--;
for (int i=l; i<s; i++) cnt1+=qs[i]==0;
for (int i=s; i<r; i++) cnt2+=qs[i]==0;
cst=min(cst, 2*min(cnt1, cnt2));
}
}
res+=cst;
}
return res;
}
/*
7 3
0 5 2 3 4 1 6
*/
