#include "books.h"
#include <bits/stdc++.h>
using namespace std;
#define TRACE(x) cout << #x << " :: " << x << endl;
#define _ << " " <<
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for(int i=(a);i>=(b);--i)
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
const int mxN = 1e6+5;
int N, S, E;
int C[mxN], L[mxN], R[mxN], cc;
void ext(int& l, int& r) {
int x = min(L[C[l]],L[C[r]]), y = max(R[C[l]],R[C[r]]);
while (true) {
if (x < l) {
--l;
x = min(x,L[C[l]]);
y = max(y,R[C[l]]);
} else if (r < y) {
++r;
x = min(x,L[C[r]]);
y = max(y,R[C[r]]);
} else break;
}
}
long long minimum_walk(std::vector<int> p, int s) {
N = SZ(p);
long long lb = 0;
cc = 0;
S = N-1, E = 0;
FOR(i,0,N-1){
lb += abs(p[i]-i);
if (C[i]) continue;
C[i] = ++cc;
L[cc] = R[cc] = i;
for (int u = p[i]; u != i; u = p[u]) {
C[u] = cc;
L[cc] = min(L[cc],u);
R[cc] = max(R[cc],u);
}
if (L[cc] != R[cc]) S = min(S,L[cc]), E = max(E,R[cc]);
}
long long add = 0;
int l = s, r = s;
ext(l,r);
while (S < l || r < E) {
bool op = 0;
int cl = 0, cr = 0, nl = -1, nr = -1;
int x = l, y = r;
while (S < x) { // calc cl
cl += 2;
ext(--x,y);
if (y > r) { op = 1; break; }
}
nl = x;
x = l, y = r;
while (y < E) { // calc cr
cr += 2;
ext(x,++y);
if (x < l) { op = 1; break; }
}
nr = y;
if (op) {
add += min(cl,cr);
} else { // neither covers
add += cl + cr;
}
l = nl, r = nr;
}
//TRACE(lb _ add);
return lb + add;
}
