#include "books.h"
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
void extend(int &l, int &r, vector<int> &C, vector<int> &L, vector<int> &R) {
int ll = min({l, L[C[l]], L[C[r]]});
int rr = max({r, R[C[l]], R[C[r]]});
while (ll < l || r < rr) {
if (ll < l) l--;
if (r < rr) r++;
ll = min({ll, L[C[l]], L[C[r]]});
rr = max({rr, R[C[l]], R[C[r]]});
}
}
int connect(int l, int r, int target_l, int target_r, vector<int> &C, vector<int> &L, vector<int> &R) {
int cost = 0;
do {
extend(l, r, C, L, R);
int cost_l = 0, cost_r = 0;
bool next_l = false;
int l_l = l, r_l = r;
while (true) {
if (l_l <= target_l) break;
l_l--;
cost_l += 2;
extend(l_l, r_l, C, L, R);
if (r < r_l) {
next_l = true;
break;
}
}
bool next_r = false;
int l_r = l, r_r = r;
while (true) {
if (target_r <= r_r) break;
r_r++;
cost_r += 2;
extend(l_r, r_r, C, L, R);
if (l_r < l) {
next_r = true;
break;
}
}
if (next_l && next_r) {
cost += min(cost_l, cost_r); // walking to shortest one, since the cycles overlap we need no additional cost
} else {
cost += cost_l + cost_r; // we must walk both ways
}
l = min(l_l, l_r);
r = max(r_l, r_r);
} while (target_l < l || r < target_r);
return cost;
}
lint minimum_walk(vector<int> p, int s) {
lint ans = 0;
int n = p.size();
vector<int> cycle(n, -1);
vector<int> L, R; // left and rightmost books in cycle
int c = 0; // cycle count
int target_l = s, target_r = s;
for (int i = 0; i < n; i++) {
ans += abs(i - p[i]);
if (cycle[i] == -1) {
L.emplace_back(i);
R.emplace_back(i);
int j = i;
do {
cycle[j] = c;
L[c] = min(L[c], j);
R[c] = max(R[c], j);
j = p[j];
} while (j != i);
if (p[i] != i) {
target_l = min(target_l, L[c]);
target_r = max(target_r, R[c]);
}
c++;
}
}
return ans + connect(s, s, target_l, target_r, cycle, L, R);
}
