#include "books.h"
#include<bits/extc++.h>
using namespace std;
const int maxn = 1<<20;
using ll = long long;
#define end orz
int vis[maxn], a[maxn], col[maxn], n, id = 0;
vector<int> cycle[maxn];
ll ans = 0;
vector<array<int, 2>> segs;
void touch(int p) {
if(vis[p]) return;
++id;
int l = p, r = p, lst = p;
while(!vis[p]) {
vis[p] = 1;
l = min(l, p);
r = max(r, p);
col[p] = id;
lst = p;
p = a[p];
ans += abs(p-lst);
}
}
int L, R, pL, pR;
void upd(int i) {
pL = min(pL, cycle[col[i]][0]);
pR = max(pR, cycle[col[i]].back());
}
void expand() {
while(pL < L || pR > R) {
while(L > pL) upd(--L);
while(R < pR) upd(++R);
}
}
int start = -1, end = -1;
template<int fl>
pair<int, int> find() {
int bl = L, br = R, cost = 0;
cout << fl << "::\n";
cout << cost << " " << L << " " << R << " TO " << endl;
while((!fl ? L == bl : R == br) && (fl ? L>start : R!=end)) {
fl ? --pL : ++pR;
++cost;
expand();
}
cout << cost << " " << L << " " << R << endl;
int nl = L, nr = R;
pL = L = bl, R = pR = br;
if(!fl ? L == nl : R == nr) return {1<<30, -1};
return {cost, fl ? nl : nr};
}
ll minimum_walk(vector<int> _a, int s) {
n = _a.size();
for(int i = 0; i < n; i++) a[i] = _a[i];
for(int i = 0; i < n; i++) {
if(a[i] != i || i == s) {
if(start == -1) start = i;
end = i;
}
touch(i);
}
for(int i = 0; i < n; i++) cycle[col[i]].push_back(i);
memset(vis, 0, sizeof vis);
pL = pR = R = s, L = s+1;
expand();
//cout << start << " " << end << " " << L << " " << R << '\n';
while(pL != start || pR != end) {
if(pL == start) {
pR++;
ans += 2;
expand();
continue;
}
if(pR == end) {
pL--;
ans += 2;
expand();
continue;
}
auto [lcst, lp] = find<1>();
auto [rcst, rp] = find<0>();
//cout << lp << " " << rp << endl;
if(lp == -1 && rp == -1) break;
if(lcst < rcst) pL = lp;
else pR = rp;
ans += 2*min(lcst, rcst);
expand();
}
return ans;
}
