#include "books.h"
#include <bits/stdc++.h>
using namespace std;
template<typename T>
using vec = vector<T>;
using ll = long long;
using vll = vec<ll>;
using pll = pair<ll,ll>;
#define pb push_back
#define dbg(x) cerr << #x << ": " << x << endl
ll minimum_walk(std::vector<int> p, int s) {
assert(s == 0);
ll n = p.size();
ll ans = 0;
for(int i = 0; i < n; i++) {
ans += abs(i-p[i]);
}
if(ans == 0) return ans;
ll cid = 0;
vll id(n,-1);
for(int i = 0; i < n; i++) {
if(id[i] != -1) continue;
ll at = i;
id[i] = ++cid;
do {
at = p[at];
id[at] = cid;
} while(at != i);
}
vll last_book(cid+1,-1);
for(ll i = 0; i < n; i++) {
last_book[id[i]] = max(last_book[id[i]],i);
}
ll last_unsorted = n-1;
for(ll i = n-1; i >= 0; i--) {
if(p[i] != i) {
last_unsorted = i;
break;
}
}
ll nextFlag = last_book[id[0]];
for(int i = 0; i <= last_unsorted; i++) {
if(i <= nextFlag) {
nextFlag = max(nextFlag, last_book[id[i]]);
} else {
dbg(i);
ans += 2;
nextFlag = last_book[id[i]];
}
}
// dbg(cid);
// for(int i = 0; i < n; i++) {
// cerr << id[i] << " ";
// } cerr << endl;
return ans;
}
