#include "books.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define rep(i , j , k) for(int i = j; i < (int)k; i++)
typedef long long ll;
const int N = 1e6 + 10;
int par[N];
ll le[N], ri[N], arr[N];
int getPar(int v) {
return v == par[v] ? v : par[v] = getPar(par[v]);
}
inline bool merge(int u , int v) {
if ((u = getPar(u)) == (v = getPar(v)))
return false;
par[v] = u;
return true;
}
inline void smax(ll &a, ll b) {
if (a < b) a = b;
}
inline void smin(ll &a, ll b) {
if (b < a) a = b;
}
long long minimum_walk(std::vector<int> p, int s) {
int n = p.size();
iota(par , par + n , 0);
vector<int> vp(n);
ll res = 0;
rep(i , 0 , n) {
res += abs(p[i] - i);
merge(i , p[i]);
vp[min(i , p[i])] = max(vp[min(i , p[i])] , max(i , p[i]));
}
int G = -1;
rep(i , 0 , n) {
if (G >= i && i != s)
merge(i , i - 1);
G = max(G , vp[i]);
}
int last = -1;
vector<pair<ll , pair<int , int>>> vec;
rep(i , 0 , n) {
if (i == p[i] && i != s) continue;
if (last == -1 || getPar(last) == getPar(i))
last = i;
else {
vec.pb({2 * (i - last) , {last , i}});
last = i;
}
}
sort(vec.begin(), vec.end());
for (auto e : vec)
if (merge(e.second.first , e.second.second))
res += e.first;
return res;
}
