#include "books.h"
using namespace std;
typedef vector<int> vi;
const int N = 1000000;
const int INF = 0x3f3f3f3f;
int min(int a, int b) { return a < b ? a : b; }
int max(int a, int b) { return a > b ? a : b; }
unsigned int X = 12345;
int rand_() {
return (X *= 3) >> 1;
}
char visited[N]; int xx[N], ll[N], rr[N], ll_[N], rr_[N], hh[N], m;
void sort(int *hh, int l, int r) {
while (l < r) {
int i = l, j = l, k = r, h = hh[l + rand_() % (r - l)], tmp;
while (j < k) {
int c = ll_[hh[j]] - ll_[h];
if (c == 0)
j++;
else if (c < 0) {
tmp = hh[i], hh[i] = hh[j], hh[j] = tmp;
i++, j++;
} else {
k--;
tmp = hh[j], hh[j] = hh[k], hh[k] = tmp;
}
}
sort(hh, l, i);
l = k;
}
}
long long minimum_walk(vi pp, int s) {
int n = pp.size(), h, h_, h1, i, j, l, r, l_, r_, cnt;
long long ans;
ans = 0;
for (i = 0; i < n; i++) {
if (i < pp[i])
ans += pp[i] - i;
else if (i > pp[i])
ans += i - pp[i];
if (!visited[i]) {
l_ = -INF, r_ = INF, l = INF, r = -INF;
while (!visited[i]) {
l = min(l, i), r = max(r, i);
if (i <= s)
l_ = max(l_, i);
if (i >= s)
r_ = min(r_, i);
visited[i] = 1, i = pp[i];
}
if (l <= s && s <= r)
ll_[m] = l_, rr_[m] = r_, ll[m] = l, rr[m] = r, m++;
else
xx[l]++, xx[r]--;
}
}
for (i = 1; i < n - 1; i++)
xx[i] += xx[i - 1];
for (i = n - 1; i > 0; i--)
xx[i] = xx[i - 1] == 0;
for (i = 1; i < n; i++)
xx[i] += xx[i - 1];
for (h = 0; h < m; h++)
hh[h] = h;
sort(hh, 0, m);
cnt = 0;
for (h = 0; h < m; h++) {
h_ = hh[h];
while (cnt && rr_[hh[cnt - 1]] < rr_[h_]) {
h1 = hh[--cnt];
ll_[h_] = max(ll_[h_], ll_[h1]), rr_[h_] = min(rr_[h_], rr_[h1]);
ll[h_] = min(ll[h_], ll[h1]), rr[h_] = max(rr[h_], rr[h1]);
}
hh[cnt++] = h_;
}
for (h = cnt - 1, l_ = s, r_ = s; h >= 0; h--) {
h_ = hh[h];
if (l_ > ll_[h_] && r_ < rr_[h_])
ans += min(xx[l_] - xx[ll_[h_]], xx[rr_[h_]] - xx[r_]) * 2;
l_ = min(l_, ll[h_]), r_ = max(r_, rr[h_]);
}
i = 0;
while (i < l_ && pp[i] == i)
i++;
j = n - 1;
while (j > r_ && pp[j] == j)
j--;
ans += (xx[l_] - xx[i] + xx[j] - xx[r_]) * 2;
return ans;
}
