#include <iostream>
#include <fstream>
#include <algorithm>
#include <cstring>
#include <climits>
#include <cassert>
#include <tuple>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <unordered_set>
#include <unordered_map>
#include <numeric>
using namespace std;
typedef long long LL;
typedef vector<int> Vi;
typedef vector<LL> VL;
typedef vector<bool> Vb;
typedef vector<vector<int>> Vii;
typedef vector<vector<vector<int>>> Viii;
typedef vector<vector<pair<int, int>>> Vip;
#define forR(i, n) for (int i = 0; i < (n); i++)
const int INF = 1 << 25;
int dist(int x1, int x2, int y1, int y2) {
int d1 = x1 - y2, d2 = x2 - y1;
if (d1 > 0 == d2 > 0)
return min(abs(d1), abs(d2));
return 0;
}
LL minimum_walk(Vi p, int s) {
int n = p.size();
LL ans = 0;
Vi g(n);
Vii gps(1); // dummy
int gn = 0; // [1, gn]
Vi gpMin(1, s), gpMax(1, s);
forR(i, n) {
if (p[i] == i) continue;
gn++;
Vi gp;
int mi = INF, ma = -1;
int h = p[i];
int pos = i;
g[i] = gn; gp.push_back(i); mi = min(mi, i); ma = max(ma, i);
while (h != i) {
ans += abs(h - pos);
pos = h;
g[h] = gn; gp.push_back(h); mi = min(mi, h); ma = max(ma, h);
swap(h, p[h]);
}
ans += abs(pos - i);
p[i] = i;
gps.push_back(gp);
gpMin.push_back(mi); gpMax.push_back(ma);
}
Vii nbs(gn + 1);
Vii nbDs(gn + 1);
for (int j = 1; j <= gn; j++) {
int d = INF;
for (int k : gps[j]) {
d = min(d, abs(k - s));
}
nbs[0].push_back(j);
nbDs[0].push_back(d);
}
for (int i = 1; i <= gn; i++) {
for (int j = 1; j <= gn; j++) {
if (i == j) continue;
nbs[i].push_back(j);
nbDs[i].push_back(dist(gpMin[i], gpMax[i], gpMin[j], gpMax[j]));
}
}
//for (int i = 1; i <= gn; i++) {
// auto& gp = gps[i];
// map<int, int> distToGp;
// distToGp[0] = INF;
// for (int j : gp) {
// distToGp[0] = min(distToGp[0], abs(j - s));
// // left
// for (int k = j - 1; k >= 0; k--) {
// if (g[k] > 0) {
// if (g[k] != g[i]) {
// // other group
// int d = abs(j - k);
// if (distToGp.count(g[k]) > 0) {
// distToGp[g[k]] = min(distToGp[g[k]], d);
// } else {
// distToGp[g[k]] = d;
// }
// }
// break;
// }
// }
// // right
// for (int k = j + 1; k < n; k++) {
// if (g[k] > 0) {
// if (g[k] != g[i]) {
// // other group
// int d = abs(j - k);
// if (distToGp.count(g[k]) > 0) {
// distToGp[g[k]] = min(distToGp[g[k]], d);
// } else {
// distToGp[g[k]] = d;
// }
// }
// break;
// }
// }
// }
// for (auto p : distToGp) {
// nbs[i].push_back(p.first);
// nbDs[i].push_back(p.second);
// }
// nbs[0].push_back(i);
// nbDs[0].push_back(distToGp[0]);
//}
// MST
LL mst = 0;
Vb vis(gn + 1);
set<pair<int, int>> minQ; // {dist, gp}
minQ.insert({ 0, 0 });
while (!minQ.empty()) {
auto t = *minQ.begin(); minQ.erase(t);
int gp = t.second;
if (vis[gp]) continue;
mst += t.first;
vis[gp] = true;
forR(i, nbs[gp].size()) {
minQ.insert({ nbDs[gp][i], nbs[gp][i] });
}
}
return ans + mst * 2;
}
#ifdef TEST_LOCAL
int main() {
auto r = minimum_walk(Vi{ 3, 2, 1, 0 }, 0);
return 0;
}
#endif
