#include "books.h"
#include <string.h>
using namespace std;
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; }
typedef vector<int> vi;
unsigned int X = 12345;
int rand_() {
return (X *= 3) >> 1;
}
char visited[N]; int xx[N], ll[N], rr[N], ll_[N], rr_[N], ii[N], m;
void sort(int *ii, int l, int r) {
while (l < r) {
int i = l, j = l, k = r, i_ = ii[l + rand_() % (r - l)], tmp;
while (j < k) {
int c = ll_[ii[j]] - ll_[i_];
if (c == 0)
j++;
else if (c < 0) {
tmp = ii[i], ii[i] = ii[j], ii[j] = tmp;
i++, j++;
} else {
k--;
tmp = ii[j], ii[j] = ii[k], ii[k] = tmp;
}
}
sort(ii, l, i);
l = k;
}
}
long long minimum_walk(vi pp, int s) {
int n = pp.size(), h, 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];
}
xx[l]++, xx[r]--;
if (l <= s && s <= r)
ll_[m] = l_, rr_[m] = r_, ll[m] = l, rr[m] = r, ii[m] = i, m++;
}
}
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];
sort(ii, 0, m);
cnt = 0;
for (h = 0; h < m; h++) {
i = ii[h];
while (cnt && rr_[ii[cnt - 1]] < rr_[i]) {
j = ii[--cnt];
ll_[i] = max(ll_[i], ll_[j]), rr_[i] = min(rr_[i], rr_[j]);
ll[i] = min(ll[i], ll[j]), rr[i] = max(rr[i], rr[j]);
}
ii[cnt++] = i;
}
for (h = cnt - 1, l_ = s, r_ = s; h >= 0; h--) {
i = ii[h];
if (l_ > ll_[i] && r_ < rr_[i])
ans += min(xx[l_] - xx[ll_[i]], xx[rr_[i]] - xx[r_]) * 2;
l_ = min(l_, ll[i]), r_ = max(r_, rr[i]);
}
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;
}
