#include "books.h"
#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define ll long long
#define pii pair <int, int>
#define pb push_back
const int N = 1e6 + 5,inf = 1e9;
int n, p[N],fix[N],l[N],r[N],cur,pr[N],idx[N],cnt,opp[N];
int tree[3][4 * N];
void build(int node, int le, int ri) {
if (le == ri) {
if (opp[le] && opp[le] >= le) tree[0][node] = opp[le];
if (opp[le] && opp[le] <= le) tree[1][node] = opp[le];
return ;
}
int mid = (le + ri) / 2;
build(2 * node, le, mid);
build(2 * node + 1, mid + 1, ri);
tree[0][node] = max(tree[0][2 * node], tree[0][2 * node + 1]);
tree[1][node] = min(tree[1][2 * node], tree[1][2 * node + 1]);
}
void update(int node, int le, int ri, int idx, int val, int ty) {
if (le > idx || ri < idx) return ;
if (le == ri) {
tree[ty][node] = val;
return ;
}
int mid = (le + ri) / 2;
update(2 * node, le, mid, idx, val, ty);
update(2 * node + 1, mid + 1, ri, idx, val, ty);
tree[0][node] = max(tree[0][2 * node], tree[0][2 * node + 1]);
tree[1][node] = min(tree[1][2 * node], tree[1][2 * node + 1]);
}
int getans(int node, int le, int ri, int start, int end, int ty) {
if (le > end || ri < start) {
return (ty == 0 ? -inf : inf);
}
if (le >= start && ri <= end) return tree[ty][node];
int mid = (le + ri) / 2;
int p1 = getans(2 * node, le, mid, start, end, ty);
int p2 = getans(2 * node + 1, mid + 1, ri, start, end, ty);
return (ty == 0 ? max(p1, p2) : min(p1, p2));
}
vector <pii> g[N];
void add_edge(int a, int b, int c) {
g[a].pb({b, c});
g[b].pb({a, c});
}
int dist[N];
int bfs01(int s, int l, int r) {
deque < int > dq;
for (int i = 1; i <= n; i++) {
dist[i] = inf;
}
dist[s] = 0;
dq.pb(s);
while (!dq.empty()) {
int vert = dq[0];
if (vert == l || vert == r) return dist[vert];
dq.pop_front();
for (pii sth : g[vert]) {
int to = sth.f, c = sth.s;
if (dist[to] > dist[vert] + c) {
dist[to] = dist[vert] + c;
if (c == 0) dq.push_front(to);
else dq.push_back(to);
}
}
}
assert(false);
}
long long minimum_walk(vector<int> perm, int s) {
s++;
n = perm.size();
long long ans = 0;
for (int i = 1; i <= n; i++) {
p[i] = perm[i - 1] + 1;
ans += (ll)abs(i - p[i]);
}
int frst_id = -1, lst_id = -1;
for (int i = 1; i <= n ;i++) {
if (p[i] != i && frst_id == -1) frst_id = i;
if (p[i] != i) lst_id = i;
}
if (frst_id == -1) {
return 0;
}
vector <pii> segs;
for (int i = 1; i <= n; i++) {
int cur = p[i];
if (!fix[i]) {
fix[i] = 1;
idx[i] = ++cnt;
l[cnt] = r[cnt] = i;
vector <int> vec;
vec.pb(i);
while (cur != i) {
vec.pb(cur);
fix[cur] = 1;
l[cnt] = min(l[cnt], cur);
r[cnt] = max(r[cnt], cur);
cur = p[cur];
}
sort(vec.begin(), vec.end());
for (int i = 1; i < (int)vec.size(); i++) {
add_edge(vec[i], vec[i - 1], 0);
segs.pb({vec[i - 1], vec[i]});
}
opp[l[cnt]] = r[cnt];
opp[r[cnt]] = l[cnt];
pr[l[cnt]]++;
pr[r[cnt]]--;
}
}
for (int i = 1; i <= n; i++) {
pr[i] += pr[i - 1];
}
for (int i = 1; i <= n; i++) {
if (pr[i] == 0 && i < lst_id && i >= frst_id) ans += 2;
else {
if (pr[i] == 0 && s <= i && i < lst_id) ans += 2;
else if (pr[i] == 0 && s > i && i >= frst_id) ans += 2;
}
}
for (int i = 1; i < n; i++) {
add_edge(i, i + 1, 1);
}
int posi = s, posj = s;
sort(segs.begin(), segs.end());
build(1, 1, n);
for (pii sth : segs) {
int l = sth.f, r = sth.s;
// Left E [l + 1, r - 1] maximum Right
int mx = getans(1, 1, n, l + 1, r - 1, 0);
if (mx > r) {
add_edge(l, mx, 0);
}
// Right E [l + 1, r - 1], minimum left
int mn = getans(1, 1, n, l + 1, r - 1, 1);
if (mn < l) {
add_edge(r, mn, 0);
}
}
int lid = 1, rid = n;
for (int i = 0; i < s; i++) {
if (!pr[i]) lid = i + 1;
}
for (int i = s; i <= n; i++) {
if (!pr[i]) { rid = i; break; }
}
int to_add = bfs01(s, lid, rid);
ans += (ll)2 * (ll)to_add;
return ans;
}
