#include "books.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> group;
vector<int> group_head, group_tail;
int find_group(int x) {
return x == group[x] ? x : group[x] = find_group(group[x]);
}
void merge_group(int x, int y) {
int gx = find_group(x), gy = find_group(y);
group_head[gx] = min(group_head[gx], group_head[gy]);
group_tail[gx] = max(group_tail[gx], group_tail[gy]);
group[gy] = gx;
}
bool is_head(int x) {
return group_head[find_group(x)] == x;
}
bool is_tail(int x) {
return group_tail[find_group(x)] == x;
}
long long minimum_walk(std::vector<int> p, int s) {
long long ans = 0;
int n = p.size();
group.assign(n, 0);
group_head.assign(n, 0);
group_tail.assign(n, 0);
for (int i = 0; i < n; i++) {
group[i] = i;
group_head[i] = i;
group_tail[i] = i;
}
for (int i = 0; i < n; i++) {
merge_group(p[i], i);
ans += abs(p[i] - i);
}
stack<int> stk;
for (int i = 0; i < n; i++) {
if (is_head(i)) {
stk.push(i);
} else {
while (find_group(stk.top()) != find_group(i)) {
merge_group(stk.top(), i);
stk.pop();
}
}
if (is_tail(i)) {
stk.pop();
}
}
int target_head = 0, target_tail = n - 1;
for (int i = 0; i < n && p[i] == i; i++) {
target_head++;
}
for (int i = n - 1; i > 0 && p[i] == i; i--) {
target_tail--;
}
int g = find_group(s);
int head = group_head[g], tail = group_tail[g];
while (head > target_head || tail < target_tail) {
int l = head, ld = 0;
while (l > target_head) {
l--;
ld++;
int lg = find_group(l);
l = group_head[lg];
if (group_tail[lg] > tail) {
break;
}
}
int r = tail, rd = 0;
while (r < target_tail) {
r++;
rd++;
int rg = find_group(r);
r = group_tail[rg];
if (group_head[rg] < head) {
break;
}
}
if (find_group(l) == find_group(r)) {
g = find_group(l);
head = group_head[g];
tail = group_tail[g];
ans += min(ld, rd) * 2;
} else {
head = l;
tail = r;
ans += ld * 2;
ans += rd * 2;
}
}
return ans;
}
