#include "books.h"
#include <bits/stdc++.h>
using namespace std;
int n, cnt[1000009];
long long solve_subtask3(vector<int>p, int s) {
n = p.size(); int maxn = 0;
for (int i = 0; i < n; i++) {
int u = i, v = p[i]; if (u > v) swap(u, v); if (u != v) { maxn = max(maxn, max(u, v)); }
cnt[u]++; cnt[v]--;
}
for (int i = 1; i <= n; i++) cnt[i] += cnt[i - 1];
long long sum = 0; for (int i = 0; i < n; i++) sum += 1LL * abs(p[i] - i);
for (int i = 0; i < maxn; i++) { if (cnt[i] == 0) sum += 2; }
return sum;
}
vector<int> G[1000009]; int cnts;
bool used[1000009]; int cl[1000009], cr[1000009];
long long solve_subtask4(vector<int> p, int s) {
n = p.size();
for (int i = 0; i < n; i++) {
if (used[i] == true) continue;
int cx = i; cl[cnts] = n - 1; cr[cnts] = 0;
while (used[cx] == false) {
used[cx] = true;
G[cnts].push_back(cx);
cl[cnts] = min(cl[cnts], cx);
cr[cnts] = max(cr[cnts], cx);
cx = p[cx];
}
cnts++;
}
for (int i = 0; i < cnts; i++) sort(G[i].begin(), G[i].end());
int pl = s, pr = s; long long totalcost = 0;
while (true) {
bool flag = false; int ret = 0;
for (int i = 0; i < cnts; i++) {
if (cl[i] == cr[i]) continue;
if (pl <= cl[i] && cr[i] <= pr) continue;
ret++;
int pos1 = lower_bound(G[i].begin(), G[i].end(), pl) - G[i].begin();
int pos2 = lower_bound(G[i].begin(), G[i].end(), pr + 1) - G[i].begin();
if (pos2 - pos1 >= 1) { pl = min(pl, cl[i]); pr = max(pr, cr[i]); flag = true; }
}
if (ret == 0) break;
if (flag == true) continue;
pair<long long, int> minx = make_pair((1 << 30), 0);
for (int i = 0; i < cnts; i++) {
if (cl[i] == cr[i]) continue;
if (pl <= cl[i] && cr[i] <= pr) continue;
int pos1 = lower_bound(G[i].begin(), G[i].end(), pl) - G[i].begin(); pos1--;
int pos2 = lower_bound(G[i].begin(), G[i].end(), pr + 1) - G[i].begin();
long long rem = (1 << 30);
if (pos1 >= 0) rem = min(rem, 1LL * pl - 1LL * G[i][pos1]);
if (pos2 < G[i].size()) rem = min(rem, 1LL * G[i][pos2] - 1LL * pr);
minx = min(minx, make_pair(rem, i));
}
totalcost += 2LL * minx.first;
pl = min(pl, cl[minx.second]);
pr = max(pr, cr[minx.second]);
}
for (int i = 0; i < n; i++) totalcost += 1LL * abs(p[i] - i);
return totalcost;
}
long long minimum_walk(vector<int> p, int s) {
if (p.size() <= 1000) return solve_subtask4(p, s);
return solve_subtask3(p, s);
}
