#include<bits/stdc++.h>
#include "books.h"
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pi;
typedef vector<pi> vpi;
typedef vector<bool> vb;
#define INF(dt) numeric_limits<dt>::max()
#define NINF(dt) numeric_limits<dt>::min()
#define pb push_back
ll minimum_walk(vi p, int s) {
int n = p.size();
/*
prune the rightmost fixed points
*/
int rm = n - 1;
while(rm == p[rm]) {
rm--;
}
n = rm + 1; // performing the pruning
// computing "connection cost"
// the cost to move between components
int connection_cost = 0;
vpi es;
for(int i = 0; i < n; i++) {
int v1 = i, v2 = p[i];
if(v1 > v2) swap(v1, v2);
es.pb({v1, 1});
es.pb({v2, -1});
// cerr << v1 << " " << v2 << endl;
}
// cerr << "EDGE END" << endl;
sort(es.begin(), es.end());
// for(int i = 0; i < (n << 1); i++) {
// cerr << es[i].first << " " << es[i].second << endl;
// }
// cerr << "ES END" << endl;
int cur_sum = 0;
for(int i = 0; i < n - 1; i++) {
cur_sum += es[(i << 1)].second;
cur_sum += es[(i << 1) | 1].second;
if(cur_sum == 0) connection_cost++;
}
// computing the base sum: the total cost to correct each component
ll base_sum = 0ll;
vb vis(n, false);
for(int i = 0; i < n; i++) {
if(vis[i]) continue;
int ci = i;
vis[ci] = true;
// int mn = ci, mx = ci;
while(p[ci] != i) {
base_sum += abs(p[ci] - ci);
ci = p[ci];
vis[ci] = true;
// mn = min(mn, ci);
// mx = max(mx, ci);
}
base_sum += abs(i - ci);
}
// cerr << base_sum << " " << (((ll)connection_cost) << 1ll) << endl;
return base_sum + (((ll)connection_cost) << 1ll);
}
