#include "books.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
vector<int> prochain;
vector<int> dejavu;
int num_compo;
vector<pair<int,int>> inter;
vector<pair<int,int>> bords;
void dfs(int pos){
if (dejavu[pos]!=0){
return ;
}
dejavu[pos]=num_compo;
inter.back().first=min(inter.back().first, pos);
inter.back().second=max(inter.back().second, pos);
dfs(prochain[pos]);
}
ll minimum_walk(vector<int> p, int depart) {
prochain=p;
int n=prochain.size();
ll rep=0;
for (int i=0;i<n;i++){
rep+=abs(i-prochain[i]);
}
dejavu.resize(n);
for (int i=0;i<n;i++){
if (dejavu[i]==0){
num_compo++;
inter.push_back({i,i});
dfs(i);
//cout<<inter.back().first<<" "<<inter.back().second<<endl;
}
}
deque<pair<int,int>> rassemble;
sort(inter.begin(), inter.end());
for (int i=1;i<(int)inter.size();i++){
if (inter[i].first<inter[i-1].second){
inter[i].first=inter[i-1].first;
inter[i].second=max(inter[i].second, inter[i-1].second);
}
else {
rassemble.push_back(inter[i-1]);
}
}
rassemble.push_back(inter.back());
while (!rassemble.empty() and rassemble.back().first==rassemble.back().second
and rassemble.back().first>depart){
rassemble.pop_back();
}
while (!rassemble.empty() and rassemble.front().first==rassemble.front().second
and rassemble.front().first<depart){
rassemble.pop_front();
}
if (depart!=0){
return depart;
}
return max(rep+((int)rassemble.size()-1)*2, (ll)0);
}
