#include "books.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> dsu;
vector<int> l;
vector<int> r;
vector<int> used;
vector<pair<int, int>> araliklar;
int goDSU(int a){
if (dsu[a] == a)
return a;
dsu[a] = goDSU(dsu[a]);
return dsu[a];
}
long long minimum_walk(std::vector<int> p, int s) {
int n = p.size();
if (p[s] == s){
int add = 1e9;
for (int i = s; i < n; i++){
if (p[i] != i){
add = i - s;
break;
}
}
for (int i = s; i > 0; i--){
if (p[i] != i){
if (add < s - i){
swap(p[s], p[s + add]);
}else{
swap(p[s], p[i]);
}
add = 0;
break;
}
}
if (add && add != 1e9){
swap(p[s], p[s + add]);
}
}
dsu.resize(n);
l.resize(n);
r.resize(n);
used.resize(n);
for (int i = 0; i < n; i++){
p[i];
dsu[i] = i;
l[i] = i;
r[i] = i;
}
int L = 0;
for (; n > 0; n--){
if (p[n - 1] != n - 1)
break;
}
if (n == 0)
return 0;
for (; L < n; L++){
if (p[L] != L)
break;
}
long long int ret = 0;
for (int i = L; i < n; i++){
ret += abs(p[i] - i);
if (goDSU(i) != goDSU(p[i])){
r[goDSU(p[i])] = max(r[goDSU(p[i])], r[goDSU(i)]);
l[goDSU(p[i])] = min(l[goDSU(p[i])], l[goDSU(i)]);
dsu[goDSU(i)] = goDSU(p[i]);
}
}
for (int i = L; i < n; i++){
if (!used[goDSU(i)]){
used[goDSU(i)] = true;
araliklar.push_back({ l[goDSU(i)], r[goDSU(i)] });
}
}
sort(araliklar.begin(), araliklar.end());
int mxr = araliklar[0].second;
for (int i = 1; i < araliklar.size(); i++){
if (mxr > araliklar[i].first){
mxr = max(mxr, araliklar[i].second);
}else{
mxr = max(mxr, araliklar[i].second);
ret += 2;
}
}
return ret;
}
