#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, L, R;
int go[mxN][2];
void ext(int& l, int& r) {
int x = l, y = r;
do {
FOR(j,0,1){
if (l >= L && go[l][j] != -1) x = min(x,go[l][j]), y = max(y,go[l][j]);
if (r < R && go[r][j] != -1) x = min(x,go[r][j]), y = max(y,go[r][j]);
}
if (x < l) --l;
if (r < y) ++r;
} while (x < l || r < y);
}
long long minimum_walk(std::vector<int> p, int s) {
N = SZ(p);
long long lb = 0;
L = N-1, R = 0;
memset(go,-1,sizeof go);
FOR(i,0,N-1){
if (i != p[i]) {
lb += abs(p[i]-i);
L = min({L,i,p[i]}), R = max({R,i,p[i]});
FOR(j,0,1) if (go[i][j] == -1) { go[i][j] = p[i]; break; }
FOR(j,0,1) if (go[p[i]][j] == -1) { go[p[i]][j] = i; break; }
}
}
long long add = 0;
int l = s, r = s;
for (;;) {
ext(l,r);
if (l <= L && r >= R) break;
add += 2;
--l, ++r;
}
//TRACE(lb _ add);
return lb + add;
}
