#include "books.h"
#include <algorithm>
using namespace std;
typedef long long llong;
const int max_n = 1000000;
const int max_cycle = 500001;
int n;
int cycle[max_n];
int cycle_l[max_cycle];
int cycle_r[max_cycle];
int group_par[max_cycle];
int cycle_n = 0;
int uf[max_cycle];
llong near[max_cycle];
llong go_left[max_cycle];
llong go_right[max_cycle];
llong go[max_cycle];
int find(int x) {
if (uf[x]) return uf[x] = find(uf[x]);
return x;
}
long long minimum_walk(vector<int> p, int s) {
llong dist1 = 0ll;
n = p.size();
for (int i = 0; i < n; ++i) {
dist1 += abs(p[i] - i);
if (p[i] != i && cycle[i] == 0) {
cycle[i] = ++cycle_n;
cycle_l[cycle[i]] = i;
cycle_r[cycle[i]] = i;
int j = p[i];
while (i != j) {
cycle[j] = cycle[i];
cycle_r[cycle[i]] = max(cycle_r[cycle[i]], j);
j = p[j];
}
}
}
if (dist1 == 0ll) return 0ll;
vector<int> st;
st.push_back(0);
for (int i = 0; i < n; ++i) {
if (p[i] != i) {
if (cycle_l[cycle[i]] == i) st.push_back(cycle[i]);
else {
int c = find(cycle[i]);
while (c < st.back()) {
int x = st.back();
st.pop_back();
uf[x] = c;
cycle_r[c] = max(cycle_r[c], cycle_r[x]);
}
if (cycle_r[c] == i) {
st.pop_back();
group_par[c] = st.back();
}
}
}
}
bool contain = false;
int right_cycle = 0;
llong dist2 = 0ll;
int l = n + 1, r = -1;
for (int i = 1; i <= cycle_n; ++i) {
group_par[i] = find(group_par[i]);
if (find(i) == i) {
l = min(l, cycle_l[i]);
r = max(r, cycle_r[i]);
if (cycle_l[i] < s && s < cycle_r[i]) contain = 1;
if (right_cycle != 0 && cycle_r[i] < cycle_r[right_cycle]) continue;
if (right_cycle != 0) dist2 += cycle_l[i] - cycle_r[right_cycle];
right_cycle = i;
}
}
if (!contain && l <= s && s <= r) return dist1 + dist2 * 2;
for (int i = 0; i < n; ++i) {
if (p[i] != i) {
int c = find(cycle[i]);
near[c] = i;
if (group_par[c] != 0 && cycle_l[c] == i)
go_left[c] = i - near[group_par[c]];
else if (cycle_r[c] == i)
near[group_par[c]] = max(near[group_par[c]], i - go_left[c]);
}
}
for (int i = n; i--;) {
if (p[i] != i) {
int c = find(cycle[i]);
near[c] = i;
if (group_par[c] != 0 && cycle_r[c] == i)
go_right[c] = near[group_par[c]] - i;
else if (cycle_l[c] == i)
near[group_par[c]] = min(near[group_par[c]], i + go_right[c]);
}
}
for (int i = 1; i <= cycle_n; ++i)
go[i] = min(go_left[i], go_right[i]) + go[group_par[i]];
llong dist3 = 1e18;
for (int i = 0; i < n; ++i) {
if (p[i] != i)
dist3 = min(go[find(cycle[i])] + abs(i - s), dist3);
}
return dist1 + (dist2 + dist3) * 2;
}
