#include "books.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1000000;
bool vis[N];
/*
bool tree[4 * N];
void push(int node)
{
if (tree[node])
{
tree[node * 2] = true;
tree[node * 2 +1] = true;
}
}
void ins(int from, int to, int a, int b, int node)
{
if (from <= a && b <= to)
{
tree[node] = true;
return;
}
push(node);
int mid = (a + b) / 2;
if (from <= mid) ins(from, to, a, mid, node * 2);
if (to > mid) ins(from, to, mid + 1, b, node * 2 + 1);
}
bool getIn(int i, int a, int b, int node)
{
if (a == b) return tree[node];
push(node);
int mid = (a + b) / 2;
if (i <= mid) return getIn(i, a, mid, node * 2);
return getIn(i, mid + 1, b, node * 2 + 1);
} */
long long minimum_walk(std::vector<int> p, int s) {
ll res = 0;
int n = p.size();
vector<array<int, 2>> ivals;
for (int i = 0; i < n; i++)
{
if (p[i] == i || vis[i]) continue;
int cur = i;
int l = cur;
int r = cur;
do
{
vis[cur] = true;
l = min(l, cur);
r = max(r, cur);
res += abs(p[cur] - cur);
//ins(min(cur, p[cur]), max(cur, p[cur]), 0, n - 1, 1);
cur = p[cur];
} while (cur != i);
ivals.push_back({l, r});
}
if (res == 0) return 0;
sort(ivals.begin(), ivals.end());
vector<array<int, 2>> together;
int l = ivals[0][0];
int r = ivals[0][1];
for (int i = 1; i < ivals.size(); i++)
{
if (ivals[i][0] > r)
{
together.push_back({l, r});
l = ivals[i][0];
r = ivals[i][1];
} else
{
r = max(ivals[i][1], r);
}
}
together.push_back({l, r});
for (int i = 1; i < together.size(); i++)
{
res += (together[i][0] - together[i - 1][1]) * 2;
}
if (s < together[0][0])
{
res += (together[0][0] - s) * 2;
}
if (s > together[together.size() - 1][1])
{
res += (s - together[together.size() - 1][1]) * 2;
}
return res;
}
/*
4 0
0 2 3 1
*/
