#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;
int segments[2][N];
bool in_range(bool dir, int pos, int le, int ri) {
if(!dir) return pos > le;
else return pos < ri;
}
bool overlap(int l1, int r1, int l2, int r2) {
return (l1<l2 && r1>r2) || (l1>r2 && r1<l2);
}
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);
}
for(int i=0; i<n; ++i) {
segments[0][i] = segments[1][i] = i;
}
for(int i=0; i<n; ++i) {
if(dsu.Find(i)==i && dsu.getl(i)!=dsu.getr(i)) {
segments[0][dsu.getl(i)] = dsu.getr(i);
segments[1][dsu.getr(i)] = dsu.getl(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--;
}
/*int pos[2] = {dsu.getl(s), dsu.getr(s)}, move[2] = {-1, 1};
while(pos[0]>le || pos[1]<ri) {
int cost[2] = {0, 0}, lim[2] = {pos[0], pos[1]};
pos[0]--; pos[1]++;
for(int dir=0; dir<2; ++dir) {
while(in_range(dir, pos[dir], le, ri) && !overlap(pos[dir], segments[dir][pos[dir]], lim[0], lim[1]) ) {
cost[dir] -= abs(pos[dir] - segments[!dir][pos[dir]]);
pos[dir] = segments[!dir][pos[dir]] + move[dir];
}
}
pos[0] = max(pos[0], le), pos[1] = min(pos[1], ri);
cost[0] += lim[0] - pos[0];
cost[1] += pos[1] - lim[1];
if(segments[0][pos[0]] == pos[1]) {
ans += min(cost[0], cost[1]) * 2;
}
else {
ans += (cost[0] + cost[1]) * 2;
}
}*/
while(true) {
int cur = -1;
for(int i=dsu.getl(s)-1; i>=le; --i) {
if(overlap(i, segments[0][i], s, s)) {
cur = i;
break;
}
}
int cost1=1, cost2=1;
int start = cur+1;
if(cur==-1) start = le, cost1=0;
for(int i=start; i<dsu.getl(s); ++i) {
cost1++;
i = segments[0][i];
}
if(cur==-1) start=ri, cost2=0;
else start=segments[0][cur]-1;
for(int i=start; i>dsu.getr(s); --i) {
cost2++;
i = segments[1][i];
}
if(cur==-1) {
ans += (cost1+cost2)*2;
break;
}
ans += min(cost1, cost2)*2;
dsu.Union(cur, s);
}
return ans;
}
