#ifdef LOCAL
#define _GLIBCXX_DEBUG
#endif
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <bitset>
#include <algorithm>
#include <cmath>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <chrono>
#include <random>
#include <complex>
#include <numeric>
#include <assert.h>
#include <functional>
#include <climits>
#include <cstring>
#include <iterator>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
using ll = long long;
using ld = long double;
using ushort = unsigned short;
#ifndef LOCAL
#define endl "\n"
#endif
#define f first
#define s second
#define vec vector
#define pii pair<int, int>
#define all(x) x.begin(), x.end()
#define pb push_back
#define mp make_pair
template<typename T1, typename T2>
istream& operator>> (istream &in, pair<T1, T2> &p) { in >> p.f >> p.s; return in; }
template<typename T1, typename T2>
ostream& operator<< (ostream &out, pair<T1, T2> p) { out << "(" << p.f << " " << p.s << ")"; return out; }
#define printv(v) cerr << #v << " "; for (auto &x : v) { cerr << x << " "; } cerr << endl;
#define printvv(v) cerr << #v << " "; for (auto &x : v) { for (auto &y : x) { cerr << y << " "; } cerr << endl; }
#define debug(x) cerr << #x << " " << x << endl;
template<typename T>
istream& operator>> (istream &in, vector<T> &v) {
for (auto &x : v) {
in >> x;
}
return in;
}
template<typename T>
ostream& operator<< (ostream &out, vector<T> v) {
for (auto &x : v) {
out << x << " ";
}
return out;
}
template<typename T>
void operator-=(vector<T> &v, int delta) {
for (auto &x : v) {
x -= delta;
}
}
template<typename T>
void operator+=(vector<T> &v, int delta) {
for (auto &x : v) {
x += delta;
}
}
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
struct DSU {
vector<int> pr, high, l, r;
DSU(vector<pii> segments) {
int n = segments.size();
pr.resize(n);
high.assign(n, 1);
iota(all(pr), 0);
l.resize(n);
r.resize(n);
for (int i = 0; i < n; ++i) {
l[i] = segments[i].f;
r[i] = segments[i].s;
}
}
int get(int v) {
if (pr[v] != v) {
pr[v] = get(pr[v]);
}
return pr[v];
}
bool unite(int a, int b) {
a = get(a);
b = get(b);
if (a == b) {
return false;
}
if (high[a] < high[b]) {
swap(a, b);
}
// cout << a << ' ' << b << endl;
pr[b] = a;
high[a] += high[b];
l[a] = min(l[a], l[b]);
r[a] = max(r[a], r[b]);
return true;
}
};
const int MAX_N = (1<<21);
struct ST {
pii T[MAX_N * 2];
vector<pii> segments;
ST() {}
void build() {
segments.pb(mp(-1e9, -1e9));
vector<pii> a(MAX_N, mp(segments.size() - 1, -1));
for (int i = 0; i < segments.size() - 1; ++i) {
if (segments[i].f == segments[i].s || segments[i].f == -segments[i].s) {
continue;
}
if (a[segments[i].f * 2].f == segments.size() - 1) {
a[segments[i].f * 2] = mp(i, segments[i].f * 2);
} else {
a[segments[i].f * 2 + 1] = mp(i, segments[i].f * 2 + 1);
}
}
build(1, 0, MAX_N, a);
}
void build(int i, int l, int r, vector<pii> &a) {
if (l + 1 == r) {
T[i] = a[l];
} else {
int m = (l + r) / 2;
build(i * 2, l, m, a);
build(i * 2 + 1, m, r, a);
T[i] = max(T[i * 2], T[i * 2 + 1], [&](const pii &a, const pii &b) {
return segments[a.f].s < segments[b.f].s;
});
}
}
pii get(int i, int l, int r, int ql, int qr) {
if (l >= qr || r <= ql) {
return mp(segments.size() - 1, 0);
}
if (ql <= l && r <= qr) {
return T[i];
} else {
int m = (l + r) / 2;
return max(get(i * 2, l, m, ql, qr), get(i * 2 + 1, m, r, ql, qr), [&](const pii &a, const pii &b) {
return segments[a.f].s < segments[b.f].s;
});
}
}
void update(int i, int l, int r, int ql) {
if (l + 1 == r) {
T[i] = mp(segments.size() - 1, -1);
return;
}
int m = (l + r) / 2;
if (m > ql) {
update(i * 2, l, m, ql);
} else {
update(i * 2 + 1, m, r, ql);
}
T[i] = max(T[i * 2], T[i * 2 + 1], [&](const pii &a, const pii &b) {
return segments[a.f].s < segments[b.f].s;
});
}
};
ST L, R;
ll minimum_walk(vector<int> p, int s) {
int n = p.size();
ll ans = 0;
vector<pii> segments;
segments.reserve(n + 1);
for (int i = 0; i < n; ++i) {
ans += abs(i - p[i]);
if (i != p[i]) {
segments.pb(mp(min(i, p[i]), max(i, p[i])));
}
}
segments.pb(mp(s, s));
sort(all(segments));
L.segments = segments;
L.build();
for (auto &x : segments) {
swap(x.f, x.s);
x.s = -x.s;
}
R.segments = segments;
R.build();
for (auto &x : segments) {
x.s = -x.s;
swap(x.f, x.s);
}
vector<int> used(segments.size());
DSU dsu(segments);
auto dfs = [&](int v, auto &&self) -> void {
if (used[v]) {
return;
}
used[v] = true;
while (true) {
pii p = L.get(1, 0, MAX_N, segments[v].f * 2, segments[v].s * 2 + 1);
if (p.f == segments.size()) {
break;
}
if (segments[p.f].s >= segments[v].s) {
dsu.unite(p.f, v);
L.update(1, 0, MAX_N, p.s);
self(p.f, self);
} else {
break;
}
}
while (true) {
pii p = R.get(1, 0, MAX_N, segments[v].f * 2, segments[v].s * 2 + 1);
if (p.f == segments.size()) {
break;
}
if (segments[p.f].f <= segments[v].f) {
dsu.unite(p.f, v);
R.update(1, 0, MAX_N, p.s);
self(p.f, self);
} else {
break;
}
}
};
for (int i = 0; i < segments.size(); ++i) {
if (segments[i].f == s && segments[i].s == s) {
continue;
}
if (!used[i]) {
dfs(i, dfs);
}
}
int leftest = s, rightest = s;
vector<int> bal(n);
for (int i = 0; i < segments.size(); ++i) {
leftest = min(leftest, segments[i].f);
rightest = max(rightest, segments[i].s);
++bal[segments[i].f];
--bal[segments[i].s];
}
int now = 0;
for (int i = 0; i < n; ++i) {
now += bal[i];
if (now == 0 && i >= leftest && i < rightest) {
ans += 2;
}
}
if (s > 0) {
vector<pii> pts;
pts.reserve(segments.size() * 2);
for (int i = 0; i < segments.size(); ++i) {
pts.pb(mp(segments[i].f, i));
pts.pb(mp(segments[i].s, i));
}
sort(all(pts));
vector<vector<pair<int, int>>> graph(segments.size());
for (int i = 1; i < pts.size(); ++i) {
graph[dsu.get(pts[i - 1].s)].pb(mp(dsu.get(pts[i].s), pts[i].f - pts[i - 1].f));
graph[dsu.get(pts[i].s)].pb(mp(dsu.get(pts[i - 1].s), pts[i].f - pts[i - 1].f));
}
int start = -1;
for (int i = 0; i < segments.size(); ++i) {
if (segments[i].f == s) {
start = dsu.get(i);
break;
}
}
priority_queue<pair<int, ll>> q;
vector<ll> d(segments.size(), 1e18);
d[start] = 0;
q.push(mp(0, start));
vector<int> marked(segments.size());
while (!q.empty()) {
int v = q.top().s;
q.pop();
if (marked[v]) {
continue;
}
marked[v] = true;
for (auto &u: graph[v]) {
if (d[u.f] > d[v] + u.s) {
d[u.f] = d[v] + u.s;
q.push(mp(-d[u.f], u.f));
}
}
}
int best = -1;
for (int i = 0; i < segments.size(); ++i) {
if (segments[i].f <= s && segments[i].s >= s && (best == -1 || segments[best].s - segments[best].f < segments[i].s - segments[i].f)) {
best = i;
}
}
ans += d[dsu.get(best)] * 2;
}
return ans;
}
