#include "books.h"
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define F first
#define S second
using namespace std;
// PixelCat was here for a night ;)
// and mango is incredibly orz
int dp[1000005], a[1000005], b[1000005], last;
long long minimum_walk(std::vector<int> p, int s)
{
int n = p.size();
ll ans = 0;
for (int i = 0; i < n; i++)
{
ans += abs(p[i] - i);
a[i] = p[i];
b[p[i]] = i;
}
for (int i = 0; i < n; i++)
a[i] = max({i, a[i], b[i]});
for (int i = 1; i < n; i++)
a[i] = max(a[i - 1], a[i]);
last = n - 1;
while (p[last] == last)
last--;
dp[0] = 0;
for (int i = 1; i < n; i++)
dp[i] = 1e9;
for (int i = 0; i < n; i++)
{
dp[i + 1] = min(dp[i + 1], dp[i] + 2);
dp[a[i]] = min(dp[a[i]], dp[i]);
}
return ans + dp[last];
}
