#include "books.h"
#include<bits/stdc++.h>
using namespace std;
int N, S, p[1000009], prv[1000009], nxt[1000009], dp[1009][1009];
bool ap[1000009];
pair < int, int > jump[1009][1009];
void update (int &x, int y)
{
if (y < x) x = y;
}
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++)
if (nxt[i] > nxt[i + 1])
nxt[i + 1] = nxt[i];
int targetL = N + 1, targetR = 0;
for (int i=1; i<=N; i++)
if (p[i] != i)
{
if (targetL == N + 1)
targetL = i;
targetR = i;
}
if (targetR == 0) return ans;
targetR = max (targetR, S);
targetL = min (targetL, S);
for (int i=1; i<=N; i++)
{
jump[i][i] = {prv[i], nxt[i]};
for (int j=i + 1; j<=N; j++)
jump[i][j].first = min (jump[i][j - 1].first, prv[j]),
jump[i][j].second = max (jump[i][j].second, nxt[j]);
}
for (int i=1; i<=N; i++)
for (int j=N; j>=i; j--)
if (jump[i][j].first != i || jump[i][j].second != j)
jump[i][j] = jump[jump[i][j].first][jump[i][j].second];
for (int i=1; i<=N; i++)
for (int j=i; j<=N; j++)
dp[i][j] = 3 * N + 10;
dp[S][S] = 0;
for (int i=S; i>=targetL; i--)
for (int j=S; j<=targetR; j++)
{
if (jump[i][j].first != i || jump[i][j].second != j)
{
update (dp[jump[i][j].first][jump[i][j].second], dp[i][j]);
continue;
}
if (j < N)
update (dp[i][j + 1], dp[i][j] + 1);
if (i > 1)
update (dp[i - 1][j], dp[i][j] + 1);
}
return ans + 2LL * dp[targetL][targetR];
}
