#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"
template<int BASE, typename COMP>
struct SEGTREE {
int n;
VPI tree;
COMP COMPOBJ;
SEGTREE(int sz) {
n = 1;
while (n < sz) n *= 2;
tree = VPI(2*n, {BASE, -1});
}
PII lav(PII a, PII b) {
if (COMPOBJ(a, b)) return a;
return b;
}
void upd(int N, int L, int R, int i, PII s) {
if (i < L || i > R) return;
if (L == R) {
tree[N] = s;
return;
}
int M = (L + R) / 2;
upd(2*N+1, L, M, i, s);
upd(2*N+2, M+1, R, i, s);
tree[N] = lav(tree[2*N+1], tree[2*N+2]);
}
PII get(int N, int L, int R, int l, int r) {
if (l <= L && R <= r) return tree[N];
if (R < l || L > r) return {BASE, -1};
int M = (L + R) / 2;
return lav(get(2*N+1, L, M, l, r), get(2*N+2, M+1, R, l, r));
}
void upd(int i, PII s) {
upd(0, 0, n-1, i, s);
}
PII get(int l, int r) {
if (l > r) return {BASE, -1};
return get(0, 0, n-1, l, r);
}
};
namespace TEST5 {
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;
SEGTREE<(int)-2e9, greater<PII>> mxval(1000);
SEGTREE<(int)+2e9, less<PII>> mnval(1000);
rep(i, n) {
auto[l, r] = ranges[i];
mxval.upd(l, {r, i});
/*cout << "AT " << l << " SAT {" << r << ", " << i << "}" << endl;*/
mnval.upd(r, {l, i});
}
/*cout << "NOW PRINTING THE GRAPH" << endl;*/
VVI gp(n);
rep(u, n) {
auto[l, r] = ranges[u];
PII p1 = mxval.get(l+1, r-1);
if (p1.ff > r) {
gp[u].pb(p1.ss);
gp[p1.ss].pb(u);
}
PII p2 = mnval.get(l+1, r-1);
if (p2.ff < l) {
gp[u].pb(p2.ss);
gp[p2.ss].pb(u);
}
}
/*cout << "ENDED" << endl;*/
dfs = [&](int u) {
comp.pb(u);
vis[u] = true;
VI harevan;
for (int v : gp[u]) if (!vis[v]) {
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));
/*int q;*/
/*cin >> q;*/
/*while (q--) {*/
/* int l, r;*/
/* cin >> l >> r;*/
/* ranges.pb({l, r});*/
/*}*/
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();
}
}
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) {
return TEST5::solve(p, s);
}
