#include "books.h"
#include<bits/stdc++.h>
using namespace std;
int nr, N, S, p[1000009], prv[1000009], nxt[1000009], lg[1000009], mi[22][1000009], ma[22][1000009];
bool ap[1000009];
pair < int, int > segm[1000009];
pair < int, int > getMiMa (int l, int r)
{
int p = lg[r - l + 1];
return {min (mi[p][l], mi[p][r - (1 << p) + 1]), max (ma[p][l], ma[p][r - (1 << p) + 1])};
}
long long minimum_walk (vector < int > pp, int ss)
{
N = pp.size (), S = ss + 1;
for (int i=1; i<=N; i++)
p[i] = pp[i - 1] + 1;
for (int i=1; i<=N; i++)
if (ap[i] == 0)
{
int j = p[i], maxRight = i;
ap[i] = 1;
while (j != i)
ap[j] = 1, maxRight = max (maxRight, j), j = p[j];
nxt[i] = maxRight, prv[i] = i, j = p[i];
while (j != i)
nxt[j] = maxRight, prv[j] = i, j = p[j];
}
long long ans = 0;
for (int i=1; i<=N; i++)
{
int curr = i - p[i];
if (curr < 0) curr = -curr;
ans += curr;
}
for (int i=1; i<=N; i++)
mi[0][i] = prv[i], ma[0][i] = nxt[i];
for (int i=1; i<=N; i++)
{
lg[i] = lg[i - 1];
if ((2 << lg[i]) <= i) lg[i] ++;
}
for (int i=1; i<=lg[N]; i++)
for (int j=1; j + (1 << i) - 1 <= N; j ++)
mi[i][j] = min (mi[i - 1][j], mi[i - 1][j + (1 << (i - 1))]),
ma[i][j] = max (ma[i - 1][j], ma[i - 1][j + (1 << (i - 1))]);
for (int i=1; i<=N; i++)
if ((i == S || i != p[i]) && ap[i] == 1)
{
int l = i, r = i;
while (1)
{
auto curr = getMiMa (l, r);
if (l == curr.first && r == curr.second) break;
l = curr.first;
r = curr.second;
}
for (int j=l; j<=r; j++)
ap[j] = 0;
segm[++nr] = {l, r};
}
for (int i=1; i<nr; i++)
ans += 2LL * (segm[i + 1].first - segm[i].second);
return ans;
}
