#include "books.h"
#include "bits/stdc++.h"
#define st first
#define nd second
#define mp make_pair
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int N = 1e6+1;
struct DSU {
int f[N], cnt[N], l[N], r[N];
DSU() {
for(int i=0; i<N; ++i) {
f[i] = l[i] = r[i] = i;
cnt[i] = 1;
}
}
int Find(int x) {
if(f[x]==x) return x;
f[x] = Find(f[x]);
return f[x];
}
void Union(int x, int y) {
x = Find(x), y = Find(y);
if(x==y) return;
if(cnt[x] < cnt[y]) swap(x, y);
cnt[x] += cnt[y];
l[x] = min(l[x], l[y]);
r[x] = max(r[x], r[y]);
f[y] = x;
}
int getl(int x) { return l[Find(x)]; }
int getr(int x) { return r[Find(x)]; }
};
DSU dsu;
ll minimum_walk(vector<int> p, int s) {
int n = p.size();
ll ans = 0;
for(int i=0; i<n; ++i) {
ans += abs(p[i] - i);
dsu.Union(i, p[i]);
}
//cerr<<ans<<'\n';
vector<int> vec;
for(int i=n-1; i>=0; --i) {
while(vec.size() && dsu.getr(i) >= vec.back()) {
if(dsu.getl(vec.back()) < i) {
dsu.Union(i, vec.back());
}
vec.pop_back();
}
vec.push_back(i);
}
int le=0, ri=n-1;
while(le<s && dsu.getl(le)==dsu.getr(le)) {
le++;
}
while(ri>s && dsu.getl(ri)==dsu.getr(ri)) {
ri--;
}
while(true) {
int l=le, r=ri, cur=-1;
int cost1=0, cost2=0;
for(int i=dsu.getl(s)-1; i>=le; --i) {
if(dsu.getr(i) > s) {
l = i;
cur = dsu.Find(i);
break;
}
}
for(int i=dsu.getr(s)+1; i<=ri; ++i) {
if(dsu.getl(i) < s) {
r = i;
break;
}
}
if(cur!=-1) l++, cost1++;
for(int i=l; i<dsu.getl(s); ++i) {
cost1++;
i = dsu.getr(i);
}
if(cur!=-1) r--, cost2++;
for(int i=r; i>dsu.getr(s); --i) {
cost2++;
i = dsu.getl(i);
}
if(cur==-1) {
ans += (cost1+cost2)*2;
break;
}
ans += min(cost1, cost2)*2;
dsu.Union(cur, s);
}
return ans;
}
