#include <bits/stdc++.h>
#define pb push_back
#include "books.h"
using namespace std;
long long minimum_walk(vector<int> p, int s) {
long long ans = 0;
int n = p.size();
vector<int> vis(n);
vector<int> on(n+1), arka(n+1);
for(int i = 0; i < n; i++){
if(vis[i] || p[i] == i) continue;
int x = i;
while(!vis[x]){
vis[x] = 1;
if(x < p[x]){
on[x]++;
on[p[x]]--;
}
else{
arka[x]++;
arka[p[x]]--;
}
x = p[x];
}
}
for(int i = 1; i <= n; i++){
on[i] += on[i-1];
}
for(int i = n-1; i >= 0; i--){
arka[i] += arka[i+1];
}
vector<int> mnval(n+1, -1), mxval(n+1, -1);
for(int i = 0; i <= n; i++){
if(on[i] == 0) continue;
if(mnval[on[i]] == -1){
mnval[on[i]] = i;
}
else{
mnval[on[i]] = min(mnval[on[i]], i);
}
if(mxval[on[i]] == -1){
mxval[on[i]] = i;
}
else{
mxval[on[i]] = max(mxval[on[i]], i);
}
}
vector<int> mnval2(n+1, -1), mxval2(n+1, -1);
for(int i = 0; i <= n; i++){
if(arka[i] == 0) continue;
if(mnval2[arka[i]] == -1){
mnval2[arka[i]] = i;
}
else{
mnval2[arka[i]] = min(mnval2[arka[i]], i);
}
if(mxval2[arka[i]] == -1){
mxval2[arka[i]] = i;
}
else{
mxval2[arka[i]] = max(mxval2[arka[i]], i);
}
}
int ind = 0;
for(int i = 1; i <= n; i++){
if(mxval[i] == -1) break;
ans += ((mxval[i] + 1) - ind);
ind = mxval[i] + 1;
ans += (ind - (mnval2[i]));
ind = mnval2[i];
}
ans += ind;
return ans;
}
