#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 {
if (l >= x) {
FOR(j,0,1) if (go[l][j] != -1) {
x = min(x,go[l][j]), y = max(y,go[l][j]);
}
--l;
}
if (r <= y) {
FOR(j,0,1) if (go[r][j] != -1) {
x = min(x,go[r][j]), y = max(y,go[r][j]);
}
++r;
}
} while (x <= l || r <= y);
l = x, 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;
int ll = l, rr = r;
do {
if (l >= 0) --l;
if (r < N) ++r;
add += 2;
if (l >= 0 && go[l][0] != -1) {
r = rr;
break;
} else if (r < N && go[r][0] != -1) {
l = ll;
break;
}
} while (true);
}
//TRACE(lb _ add);
return lb + add;
}
