#include <bits/stdc++.h>
#include "books.h"
using namespace std;
int find(int x, vector<int> &p)
{
return (x == p[x]) ? x : p[x] = find(p[x], p);
}
void search(int x, vector<int> &group, vector<int> &L, vector<int> &R, vector<int> &occ, vector<int> &P, vector<int> &Tab, int &cur)
{
occ[x] = 1;
int until = R[x];
while (cur <= until)
{
if (find(group[Tab[cur]], P) == find(x, P))
{
cur++;
continue;
}
if (R[find(group[Tab[cur]], P)] > until)
{
R[find(x, P)] = max(R[find(x, P)], R[find(group[Tab[cur]], P)]);
L[find(x, P)] = min(L[find(x, P)], L[find(group[Tab[cur]], P)]);
P[find(group[Tab[cur]], P)] = find(x, P);
until = R[find(x, P)];
cur++;
}
else
{
search(group[Tab[cur]], group, L, R, occ, P, Tab, cur);
}
}
}
long long minimum_walk(vector<int> p, int s)
{
int N = p.size();
long long ans = 0;
vector<int> group(N), occ(N), L, R, P;
int buff = 0;
for (int i = 0; i < N; i++)
{
if (occ[i])
continue;
P.push_back(buff);
int x = i;
occ[x] = 1;
group[x] = buff;
ans += abs(p[x] - x);
x = p[x];
L.push_back(i);
int maxx = i;
while (x != i)
{
maxx = max(maxx, x);
occ[x] = 1;
group[x] = buff;
ans += abs(p[x] - x);
x = p[x];
}
R.push_back(maxx);
buff++;
}
occ.assign(buff, 0);
int cur = 0;
for (int i = 0; i < N; i++)
{
if (occ[find(group[i], P)])
continue;
search(group[i], group, L, R, occ, P, p, cur);
}
for (int i = 0; i < N; i++)
group[i] = find(group[i], P);
int pos = L[group[s]];
int l = 0, r = N - 1;
while (l < N && p[l] == l)
l++;
while (r >= 0 && p[r] == r)
r--;
while (pos > l)
{
ans += 2;
pos = L[group[pos - 1]];
}
pos = R[group[s]];
while (pos < r)
{
ans += 2;
pos = R[group[pos + 1]];
}
return ans;
}
