#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define replr(i, a, b) for (int i = int(a); i <= int(b); ++i)
#define reprl(i, a, b) for (int i = int(a); i >= int(b); --i)
#define rep(i, n) for (int i = 0; i < int(n); ++i)
#define mkp(a, b) make_pair(a, b)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<PII> VPI;
typedef vector<VI> VVI;
typedef vector<VVI> VVVI;
typedef vector<VPI> VVPI;
typedef pair<ll, ll> PLL;
typedef vector<ll> VL;
typedef vector<PLL> VPL;
typedef vector<VL> VVL;
typedef vector<VVL> VVVL;
typedef vector<VPL> VVPL;
template<class T> T setmax(T& a, T b) {if (a < b) return a = b; return a;}
template<class T> T setmin(T& a, T b) {if (a < b) return a; return a = b;}
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template<class T>
using indset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#include "books.h"
namespace TEST1 {
map<VI, int> ans = {
{{2, 3, 0, 1}, 8},
{{2, 3, 1, 0}, 8},
{{3, 2, 0, 1}, 8},
{{3, 2, 1, 0}, 8},
{{1, 0}, 2},
{{}, 0}
};
ll solve(VI p, int S) {
while (p.size() && p.back() == p.size()-1) p.pop_back();
if (ans.count(p)) return ans[p];
if (p.size() == 4) return 6;
if (p.size() == 3) return 4;
return ans[p];
}
};
namespace TEST2 {
ll solve(VI p, int s) {
int n = p.size();
VI vis(n);
int upto = 0;
ll ans = 0;
rep(u, n) if (!vis[u]) {
int v = u;
if (v == p[v]) {
vis[v] = true;
continue;
}
if (v > upto) ans += 2*(v-upto);
do {
vis[v] = true;
setmax(upto, v);
ans += abs(p[v]-v);
v = p[v];
} while (v != u);
}
return ans;
}
};
namespace TEST4 {
int s;
VI p;
VI vis, group;
ll ans;
map<PII, VI> comps;
PII getcomp(int s) {
PII ret{s, s};
int u = s;
VI vec;
do {
vec.pb(u);
vis[u] = true;
setmin(ret.ff, u);
setmax(ret.ss, u);
ans += abs(p[u]-u);
u = p[u];
} while (u != s);
for (int u : vec) comps[ret].pb(u);
return ret;
}
PII skizbp;
void compressranges(VPI& ranges) {
int n = ranges.size();
VI vis(n);
function<void(int)> dfs;
VI comp;
dfs = [&](int u) {
comp.pb(u);
vis[u] = true;
rep(v, n) if (!vis[v]) {
if (ranges[v].ss < ranges[u].ff || ranges[v].ff > ranges[u].ss) continue;
if (ranges[u].ff < ranges[v].ff && ranges[v].ss < ranges[u].ss) continue;
if (ranges[v].ff < ranges[u].ff && ranges[u].ss < ranges[v].ss) continue;
dfs(v);
}
};
if (true) {
VPI tmp;
rep(u, n) if (!vis[u]) {
comp.clear();
dfs(u);
PII ret = {+2e9, -2e9};
for (int u : comp) {
setmin(ret.ff, ranges[u].ff);
setmax(ret.ss, ranges[u].ss);
}
VI vec;
for (int u : comp) {
for (int x : comps[ranges[u]]) {
vec.pb(x);
}
}
comps[ret].clear();
for (int x : vec) comps[ret].pb(x);
if (u == 0) skizbp = ret;
tmp.pb(ret);
}
ranges = tmp;
}
sort(all(ranges));
PII glxavor = {s, s};
int cur = -1;
VPI roots;
while (true) {
auto it = upper_bound(all(ranges), PII{cur, +2e9});
if (it == ranges.end()) break;
roots.pb(*it);
if (it->ff <= s && s <= it->ss) {
glxavor = *it;
}
cur = it->ss;
}
replr(i, 1, roots.size()-1) {
ans += (roots[i].ff - roots[i-1].ss)*2;
}
VPI tmp{glxavor};
for (PII p : ranges) {
if (glxavor.ff < p.ff && p.ss < glxavor.ss) {
tmp.pb(p);
}
}
ranges = tmp;
}
ll solve(VI PARG, int SARG) {p = PARG, s = SARG;
VPI ranges;
vis = VI(p.size());
group = VI(p.size(), -1);
ranges.pb(getcomp(s));
rep(u, p.size()) if (u != p[u] && !vis[u]) ranges.pb(getcomp(u));
compressranges(ranges);
sort(all(ranges), [&](PII a, PII b){
swap(a.ff, a.ss);
swap(b.ff, b.ss);
return a < b;
});
int n = ranges.size();
VPI points;
rep(i, n) {
for (int x : comps[ranges[i]]) {
points.pb({x, i});
}
}
sort(all(points));
VVPI gp(n);
rep(u, n) {
auto[l, r] = ranges[u];
VPI::iterator(it);
it = upper_bound(all(points), PII{r, +2e9});
if (it != points.end()) {
gp[u].pb({it->ss, (it->ff-r)*2});
}
it = lower_bound(all(points), PII{l, -2e9});
if (it != points.begin()) {it--;
gp[u].pb({it->ss, (l-it->ff)*2});
}
}
int start = -1;
rep(i, n) if (ranges[i] == skizbp) start = i;
priority_queue<PLL> pq;
VL dist(n, 1e18);
VI vis(n);
pq.push({0, start});
dist[start] = 0;
while (pq.size()) {
int u = pq.top().ss;
pq.pop();
if (vis[u]) continue;
vis[u] = true;
for (auto[v, w] : gp[u]) {
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
pq.push({-dist[v], v});
}
}
}
return ans + dist.back();
}
}
ll minimum_walk(VI p, int s) {
if (s == 0) return TEST2::solve(p, s);
return TEST4::solve(p, s);
}
