#include "books.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ii = pair<int, int>;
#define X first
#define Y second
int n;
bool vis[1000007];
ii I[1000007];
int minv[21][1000007], maxv[21][1000007];
int maxk[1000007];
int getmin(int a, int b) {
int l = (b - a + 1);
return min(minv[maxk[l]][a], minv[maxk[l]][b - (1 << maxk[l]) + 1]);
}
int getmax(int a, int b) {
int l = (b - a + 1);
return max(maxv[maxk[l]][a], maxv[maxk[l]][b - (1 << maxk[l]) + 1]);
}
ii extend(int a, int b) {
int na = min(a, getmin(a, b));
int nb = max(b, getmax(a, b));
if((ii){na, nb} == (ii){a, b})
return {a, b};
return extend(na, nb);
}
int dist_left(int x, int y) {
if(x <= y)
return 0;
if(I[x].X < x)
return dist_left(I[x].X, y);
return 1 + dist_left(x - 1, y);
}
int dist_right(int x, int y) {
if(x >= y)
return 0;
if(I[x].Y > x)
return dist_right(I[x].Y, y);
return 1 + dist_right(x + 1, y);
}
long long minimum_walk(std::vector<int> p, int s) {
ll res = 0;
n = p.size();
for(int i = 0 ; i < n ; i++) {
if(vis[i])
continue;
vector<int> tmp;
int minx = 1e9, maxx = -1;
int w = i;
while(!vis[w]) {
vis[w] = 1;
res += abs(p[w] - w);
minx = min(minx, w);
maxx = max(maxx, w);
tmp.push_back(w);
w = p[w];
}
for(int x : tmp)
I[x] = {minx, maxx};
}
for(int i = 0 ; i < n ; i++)
minv[0][i] = maxv[0][i] = p[i];
for(int k = 1 ; k < 20 ; k++) {
for(int i = 0 ; i + (1 << k) <= n ; i++) {
minv[k][i] = min(minv[k - 1][i], minv[k - 1][i + (1 << (k - 1))]);
maxv[k][i] = max(maxv[k - 1][i], maxv[k - 1][i + (1 << (k - 1))]);
}
}
int k = 0;
for(int i = 1 ; i <= n ; i++) {
if((1 << (k + 1)) <= i)
k++;
maxk[i] = k;
}
int begin = 0;
while(begin < n && p[begin] == begin)
begin++;
if(begin == n)
return 0;
int end = n - 1;
while(p[end] == end)
end--;
int a = extend(s, s).X, b = extend(s, s).Y;
while(a > begin || b < end) {
int lbook = a - 1;
while(lbook >= 0 && I[lbook].Y < s)
lbook--;
if(lbook == -1) {
res += 2 * dist_left(a, begin);
res += 2 * dist_right(b, end);
a = begin;
b = end;
continue;
}
int rbook = b + 1;
while(I[rbook].X > s)
rbook++;
if(dist_left(a, lbook) < dist_right(b, rbook)) {
res += 2 * dist_left(a, lbook);
} else {
res += 2 * dist_right(b, rbook);
}
ii r = extend(lbook, rbook);
a = r.X;
b = r.Y;
}
//~ for(int i = 0 ; i < n ; i++)
//~ cout << I[i].X << " " << I[i].Y << endl;
return res;
}
