#include <bits/stdc++.h>
#include "books.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define fi first
#define se second
#define mp make_pair
int n;
const int N = (int)1e6 + 100;
int lef[N], rig[N];
bool vis[N];
bool has[N];
int tl, tr;
void extend(int &li, int &ri){
int ni = min(lef[li],lef[ri]);
int nj = max(rig[li],rig[ri]);
while(li > ni || ri < nj){
if(li > ni){
li--;
ni = min(ni, lef[li]);
nj = max(nj, rig[li]);
}
else{
ri++;
ni = min(ni, lef[ri]);
nj = max(nj, rig[ri]);
}
}
}
int disl[N];
int disr[N];
int st;
int solve(int li, int ri){
int cnt = 0;
extend(li, ri);
int ai, aj;
while(li != tl || ri != tr){
if(li == tl){
cnt += 2;
ri ++ ;
}
else if(ri == tr){
cnt += 2;
li -- ;
}
else{
int il = li;
int ir = ri;
int ca = 0;
bool valid = false;
int low=li, high=ri;
while(il > tl){
il--;
ca += 2;
extend(il, ir);
if(ir > ri){
valid = true;
break;
}
}
if(!valid){
li=tl;
cnt+=ca;
break;
}
low = min(low, il);
high = max(high, ir);
il = li;
ir = ri;
int cb = 0;
valid = false;
while(ir < tr){
ir++;
cb += 2;
extend(il, ir);
if(il < li){
valid = true;
break;
}
}
if(!valid){
ri=tr;
cnt += cb;
extend(li, ri);
continue;
}
low = min(low, il);
high = max(high, ir);
cnt += min(ca, cb);
li = low;
ri = high;
}
extend(li,ri);
}
return cnt;
}
long long minimum_walk(vector<int> p, int s) {
n = p.size();
st = s;
int id;
int low, high;
ll sol = 0;
tl = tr = s;
for(int i = 0 ; i < n; i ++ ){
sol += abs(p[i] - i);
if(!vis[i]){
vector<int> cyc;
id = i;
while(!vis[id]){
vis[id]=true;
cyc.push_back(id);
id=p[id];
}
low = n-1;
high = 0;
for(auto x : cyc){
low = min(low, x);
high = max(high, x);
}
for(auto x : cyc){
lef[x] = low;
rig[x] = high;
}
}
if(p[i] != i){
tl = min(tl, i);
tr = max(tr, i);
}
}
return sol + solve(s, s);
}
