#include "books.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const ll INF=1e9+7;
const int LIM=1e6+7;
ll F[LIM], mi[LIM], ma[LIM], l, r;
set<ll>S;
ll fnd(ll x) {
if(F[x]==x) return x;
return F[x]=fnd(F[x]);
}
void uni(int a, int b) {
if(fnd(a)==fnd(b)) return;
ma[fnd(a)]=max(ma[fnd(a)], ma[fnd(b)]);
mi[fnd(a)]=min(mi[fnd(a)], mi[fnd(b)]);
F[fnd(b)]=fnd(a);
}
ll solve(ll aktl, ll aktr, ll aktmi, ll aktma) {
if(aktl>aktmi) {
--aktl;
aktmi=min(aktmi, mi[fnd(aktl)]);
aktma=max(aktma, ma[fnd(aktl)]);
return solve(aktl, aktr, aktmi, aktma);
}
if(aktr<aktma) {
++aktr;
aktmi=min(aktmi, mi[fnd(aktr)]);
aktma=max(aktma, ma[fnd(aktr)]);
return solve(aktl, aktr, aktmi, aktma);
}
if(aktl==l && aktr==r) return 0;
ll xl=aktl, xr=aktr, xmi=aktmi, xma=aktma, xans=0;
while(xl>l) {
--xl;
if(xl<xmi) xans+=2;
xmi=min(xmi, mi[fnd(xl)]);
xma=max(xma, ma[fnd(xl)]);
if(xma>xr) break;
}
if(xma==xr && aktl!=l) return solve(xl, xr, xmi, xma)+xans;
ll yl=aktl, yr=aktr, ymi=aktmi, yma=aktma, yans=0;
while(yr<r) {
++yr;
if(yr>yma) yans+=2;
ymi=min(ymi, mi[fnd(yr)]);
yma=max(yma, ma[fnd(yr)]);
if(ymi<yl) break;
}
if(ymi==yl && aktr!=r) return solve(yl, yr, ymi, yma)+yans;
return solve(yl, yr, ymi, yma)+min(xans, yans);
}
ll minimum_walk(vector<int>p, int s) {
ll n=p.size();
rep(i, n) {
F[i]=ma[i]=mi[i]=i;
S.insert(i);
}
rep(i, n) uni(i, p[i]);
vector<pair<pair<ll,ll>,pair<ll,ll>>>V;
l=0; r=n-1;
while(l<s && p[l]==l) ++l;
while(r>s && p[r]==r) --r;
ll ans=0;
rep(i, n) ans+=abs(p[i]-i);
return ans+solve(s, s, mi[fnd(s)], ma[fnd(s)]);
}
