#include <bits/stdc++.h>
#include "books.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define sep ' '
#define X first
#define Y second
#define all(x) (x).begin() , (x).end()
#define SZ(x) int(x.size())
const int MAXN = 1e6 + 10;
int n , mark[MAXN] , mx[MAXN] , mn[MAXN] , par[MAXN] , sz[MAXN];
ll ans , ps[MAXN];
vector<int> comp[MAXN];
int Find(int v){
return (par[v] == -1 ? v : par[v] = Find(par[v]));
}
void Union(int v , int u){
v = Find(v); u = Find(u);
if(v == u) return;
if(sz[v] < sz[u]) swap(v , u);
par[u] = v;
sz[v] += sz[u];
mx[v] = max(mx[v] , mx[u]);
mn[v] = min(mn[v] , mn[u]);
}
int count(int l , int r , int x){
int ans = 0;
for(int i = l ; i < r ; i++){
ans += (ps[i] == x);
}
return ans;
}
ll minimum_walk(vector<int> p, int s) {
fill(mx , mx + MAXN , -1);
fill(mn , mn + MAXN , MAXN);
fill(par , par + MAXN , -1);
fill(sz , sz + MAXN , 1);
n = p.size();
vector<pii> vec;
for(int i = 0 ; i < n ; i++){
ans += abs(i - p[i]);
if(mark[i]) continue;
int x = i , flag = 0;
vector<int> v;
while(!mark[x]){
mark[x] = 1; mn[x] = mx[x] = x;
v.push_back(x);
x = p[x];
}
sort(all(v));
for(int j = 0 ; j + 1 < SZ(v) ; j++){
Union(v[j] , v[j + 1]);
vec.push_back({v[j] , v[j + 1]});
}
}
vector<int> stk;
sort(all(vec));
for(int i = 0 ; i < SZ(vec) ; i++){
while(SZ(stk) > 0 && vec[i].Y > vec[stk.back()].Y){
if(vec[i].X < vec[stk.back()].Y) Union(vec[i].X , vec[stk.back()].X);
stk.pop_back();
}
stk.push_back(i);
}
vector<int> v;
for(int i = 0 ; i < n ; i++){
comp[Find(i)].push_back(i);
if(Find(i) == i){
ps[mn[i]]++; ps[mx[i]]--;
if(mn[i] <= s && s <= mx[i]){
v.push_back(i);
}
}
}
partial_sum(ps , ps + MAXN , ps);
int l = 0 , r = n;
while(l < s && ps[l] == 0) l++;
while(s <= r && ps[r] == 0) r--;
ans += 2 * count(l , r + 1 , 0);
for(int i = 0 ; i + 1 < SZ(v) ; i++){
int l2 = mn[v[i + 1]] , r2 = mx[v[i + 1]];
int l1 = (*prev(lower_bound(all(comp[v[i]]) , l2)));
int r1 = (*lower_bound(all(comp[v[i]]) , r2));
// cout << l1 << sep << l2 << sep << r1 << sep << r2 << endl;
ans += min(count(l1 , l2 , i + 1) , count(r2 , r1 , i + 1)) * 2;
}
return ans;
}
