#include "books.h"
#include <algorithm>
#define long long long
using namespace std;
const int N = 1e6 + 2;
vector<int> p;
int gr[N], boundL[N], boundR[N];
void Dfs(int u)
{
if (gr[p[u]] == -1)
{
gr[p[u]] = gr[u];
Dfs(p[u]);
}
boundL[gr[u]] = min(boundL[gr[u]], u);
boundR[gr[u]] = max(boundR[gr[u]], u);
}
long minimum_walk(std::vector<int> p_, int s) {
p = p_;
int n = p.size(), L = 0, R = n - 1;
while (R > s && p[R] == R) --R;
while (L < s && p[L] == L) ++L;
fill(gr + L, gr + R + 1, -1);
for (int i = 0; i < n; ++i)
boundL[i] = n, boundR[i] = 0;
long ans = 0;
for (int i = L; i <= R; ++i)
{
if (gr[i] == -1) gr[i] = i, Dfs(i);
ans += abs(i - p[i]);
}
int curL = s, curR = s;
while (curL != L || curR != R)
{
int newL, newR;
if (curL > boundL[gr[s]] || curR < boundR[gr[s]]) // first time
{
newL = boundL[gr[s]], newR = boundR[gr[s]];
}
else
{
ans += 2;
newL = curL - (curL > L), newR = curR + (curR < R);
}
while (curL != newL || curR != newR)
{
if (curL > newL)
{
--curL;
newL = min(newL, boundL[gr[curL]]);
newR = max(newR, boundR[gr[curL]]);
}
else
{
++curR;
newL = min(newL, boundL[gr[curR]]);
newR = max(newR, boundR[gr[curR]]);
}
}
}
int valL = 0, valR = 0;
for (int i = L, mx = 0; i < s; ++i)
{
mx = max(mx, p[i]);
if (mx == i) valL += 2;
}
for (int i = R, mn = n; i > s; --i)
{
mn = min(mn, p[i]);
if (mn == i) valR += 2;
}
return ans + min(valL, valR);
}
