#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();
long long int ret = 0;
if (p[s] == s){
int add = 1e9;
cerr << add << endl;
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){
add = s - i;
}
break;
}
}
if (add != 1e9)
ret += add * 2;
}
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;
}
for (int i = 0; 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 = 0; i < n; i++){
if (!used[goDSU(i)] && l[goDSU(i)] != r[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{
ret += (araliklar[i].second - mxr) * 2;
mxr = max(mxr, araliklar[i].second);
}
}
return ret;
}
