#include "books.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (l); --x)
typedef long long ll;
typedef std::pair<int,int> pii;
using namespace std;
const int N = 1e6+10;
bool vis[N];
int mn[N], mx[N];
int n;
void Do(const vector<int> &p, int i) {
int x = i, y = i;
vector<int> vec;
while (!vis[i]) {
vec.push_back(i);
vis[i] = 1;
x = min(x, i);
y = max(y, i);
i = p[i];
}
for (int j : vec) {
mn[j] = x;
mx[j] = y+1;
}
}
int l, r, pl, pr;
void go() {
while (l < pl || pr < r) {
while (l < pl) {
--pl;
l = min(l, mn[pl]);
r = max(r, mx[pl]);
}
while (pr < r) {
l = min(l, mn[pr]);
r = max(r, mx[pr]);
++pr;
}
}
}
pii try_left() {
int cl = l;
int ans = 0;
LoopR (i,0,l) {
while (i < cl) {
++ans;
--cl;
}
if (mx[i] > r)
return {ans, i};
cl = min(cl, mn[i]);
}
return {INT_MAX, -1};
}
pii try_right() {
int cr = r;
int ans = 0;
Loop (i,r,n) {
while (cr <= i) {
++ans;
++cr;
}
if (mn[i] < l)
return {ans, i};
cr = max(cr, mx[i]);
}
return {INT_MAX, n};
}
void trim(vector<int> &p, int &s) {
int p0 = 0, p1 = p.size()-1;
while (p0 < s && p[p0] == p0)
++p0;
while (s < p1 && p[p1] == p1)
--p1;
vector<int> ans(p1-p0+1);
Loop (i,p0,p1+1)
ans[i-p0] = p[i]-p0;
p = ans;
s = s-p0;
}
long long minimum_walk(std::vector<int> p, int s) {
trim(p, s);
n = p.size();
Loop (i,0,n) {
if (!vis[i])
Do(p, i);
}
int ans = 0;
l = s;
r = s+1;
pl = s;
pr = s;
go();
for (;;) {
auto [x, xi] = try_left();
auto [y, yi] = try_right();
//cerr << x << ' ' << y << '\n';
if (x == INT_MAX && y == INT_MAX)
break;
if (x < y) {
ans += x;
l = xi;
} else {
ans += y;
r = yi+1;
}
go();
}
while (0 < l) {
--l;
++ans;
go();
}
while (r < n) {
++r;
++ans;
go();
}
ans *= 2;
Loop (i,0,n)
ans += abs(i - p[i]);
return ans;
}
