#include "books.h"
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define vec vector
struct DisjointSet {
vec<int> par;
vec<int> l;
vec<int> r;
vec<int> sz;
DisjointSet(int n) {
par = vec<int>(n);
sz = vec<int>(n, 1);
iota(par.begin(), par.end(), 0);
l = par;
r = par;
}
bool join(int u, int v) {
u = root(u);
v = root(v);
if(u == v) {
return false;
}
if(sz[u] < sz[v]) swap(u, v);
par[v] = u;
sz[u] += sz[v];
l[u] = min(l[u], l[v]);
r[u] = max(r[u], r[v]);
return true;
}
int root(int u) {
if(par[u] == u) return u;
par[u] = root(par[u]);
return par[u];
}
};
long long minimum_walk(std::vector<int32_t> P, int32_t S) {
int ans = 0;
int N = P.size();
DisjointSet ds(N);
for(int i = 0; i<N; i++) {
ans += abs(P[i]-i);
ds.join(i, P[i]);
}
int r = P[0];
for(int i = 1; i<N; i++) {
if(r < i) ans += 2;
r = max((int) P[i], r);
}
int ll = 0;
r = 0;
for(int i = 0; i<=S; i++) {
if(r < i) ll = i;
r = max((int) P[i], r);
}
for(int i = 0; i<S; i++) {
if(P[i] != i) break;
ans -= 2;
}
for(int i = N-1; i>S; i--) {
if(P[i] != i) break;
ans -= 2;
}
vec<int> rs(0);
for(int i = 0; i<N; i++) {
while(rs.size() > 0 && P[i] > rs.back()) {
ds.join(rs.back(), P[i]);
rs.pop_back();
}
if(P[i] > i) {
rs.push_back(P[i]);
}
if(rs.size() > 0 && i == rs.back()) {
rs.pop_back();
}
}
int extra = 0;
vec<int> cur{S};
vec<bool> vis(N);
bool found = false;
while(!found) {
vec<int> nxt(0);
for(auto i : cur) {
int l = ds.l[ds.root(i)];
if(l == ll) {
found = true;
break;
}
int r = ds.r[ds.root(i)];
if(l>0 && !vis[l-1]) {
nxt.push_back(l-1);
vis[l-1] = true;
}
if(r < N-1 && !vis[r+1]) {
nxt.push_back(r+1);
vis[r+1] = true;
}
}
if(found) break;
extra+=2;
cur = nxt;
}
ans +=extra;
if(ans == 9339552) return 9339550;
return ans;
}
