#include "books.h"
#include<bits/stdc++.h>
#define fr first
#define sc second
#define LL long long
#define all(s) s.begin(), s.end()
using namespace std;
const int nmax = 1000005;
long long n, comp, l_ned, r_ned, ans, viz[nmax];
vector<long long>cicles[nmax];
void extend(LL &l, LL &r, LL &ll, LL &rr){
while(l > ll || r < rr){
if(l > ll){
--l;
ll = min(ll, cicles[viz[l]][0]);
rr = max(rr, cicles[viz[l]].back());
}
else if(r < rr){
++r;
ll = min(ll, cicles[viz[r]][0]);
rr = max(rr, cicles[viz[r]].back());
}
}
}
void compute(int s){
LL l = s, r = s, ll = cicles[viz[s]][0], rr = cicles[viz[s]].back();
extend(l, r, ll, rr);
while(ll > 0 || rr < n - 1){
LL calcright = 0, maxi = -1, findright = 0;
for(int i=rr+1;i<=n-1;i++){
if(i == cicles[viz[i]][0] && i > maxi){
calcright += 2LL;
}
maxi = max(maxi, cicles[viz[i]].back());
if(cicles[viz[i]][0] < ll){
findright = viz[i];
break;
}
}
if(!findright){
rr = n - 1;
ans += calcright;
}
LL calcleft = 0, mini = n, findleft = 0;
for(int i=ll-1;i>=0;i--){
if(i == cicles[viz[i]].back() && i < mini){
calcleft += 2LL;
}
mini = min(mini, cicles[viz[i]][0]);
if(cicles[viz[i]].back() > rr){
findleft = viz[i];
break;
}
}
if(!findleft){
ll = 0;
ans += calcleft;
}
else{
ans += min(calcleft, calcright);
if(calcleft > calcright){
ll = min(ll, cicles[findright][0]);
rr = max(rr, cicles[findright].back());
}
else{
ll = min(ll, cicles[findleft][0]);
rr = max(rr, cicles[findleft].back());
}
}
}
}
long long minimum_walk(vector<int> p, int s) {
n = (int)p.size();
while(p[l_ned] == l_ned && s > l_ned) l_ned++;
r_ned = n - 1;
while(p[r_ned] == r_ned && s < r_ned) r_ned--;
vector<int>aux;
for(int i=l_ned;i<=r_ned;i++){
aux.push_back(p[i] - l_ned);
}
swap(aux, p);
s -= l_ned;
n = (int)p.size();
for(int i=0;i<n;i++){
ans += abs(i - p[i]);
}
for(int i=0;i<n;i++){
if(!viz[i]){
++comp;
viz[i] = comp;
cicles[comp].push_back(i);
int curr = p[i];
while(curr != i){
viz[curr] = comp;
cicles[comp].push_back(curr);
curr = p[curr];
}
}
}
for(int i=1;i<=comp;i++){
sort(all(cicles[i]));
}
compute(s);
return ans;
}
