#include <bits/stdc++.h>
#include "books.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define fi first
#define se second
#define mp make_pair
int n;
const int N = (int)1e6 + 10;
int lef[N], rig[N];
bool vis[N];
bool has[N];
long long minimum_walk(vector<int> p, int s) {
n = p.size();
int id;
int low, high;
ll sol = 0;
for(int i = 0 ; i < n; i ++ ){
sol += abs(p[i] - i);
if(!vis[i]){
vector<int> cyc;
id = i;
while(!vis[id]){
vis[id]=true;
cyc.push_back(id);
id=p[id];
}
low = n-1;
high = 0;
for(auto x : cyc){
low = min(low, x);
high = max(high, x);
}
for(auto x : cyc){
lef[x] = low;
rig[x] = high;
}
}
}
for(int i = 0 ; i < n ;i ++ ){
if(i)
rig[i] = max(rig[i], rig[i - 1]);
}
for(int i = n-1; i >= 0 ; i -- ){
if(p[i] != i) has[i]=true;
has[i]|=has[i+1];
}
for(int i = n-2; i >= 0 ; i -- ){
if(i)
lef[i] = min(lef[i], lef[i + 1]);
}
for(int i = 0 ; i + 1 < n; i ++ ){
if(rig[i] <= i && lef[i + 1] > i && has[i+1]){
sol += 2;
}
}
return sol;
}
