#include "books.h" #include <bits/stdc++.h> using ll = long long; using namespace std; long long minimum_walk(std::vector<int> p, int s) { int n = p.size(); vector<ll> l; vector<ll> r; int cyc = 0; ll sol = 0; vector<bool> vis(n, 0); for(int i = 0; i<n; i++){ if(vis[i]) continue; cyc++; l.push_back(i); r.push_back(i); ll v = i; while(!vis[v]){ vis[v] = 1; l.back() = min(l.back(), v); r.back() = max(r.back(), v); sol += (ll)abs(p[v]-v); v = p[v]; } } // cerr << cyc << '\n'; // cerr << sol << '\n'; ll l_curr = s; ll r_curr = s; vector<int> left_c; vector<int> right_c; for(int i = 0; i<cyc; i++){ if(l[i] == r[i]) continue; if(l[i] <= s && r[i] >= i){ l_curr = min(l_curr, l[i]); r_curr = max(r_curr, r[i]); } else if(r[i] < s) left_c.push_back(i); else right_c.push_back(i); } sort(left_c.begin(), left_c.end(), [&](int a, int b){return r[a] > r[b];}); sort(right_c.begin(), right_c.end(), [&](int a, int b){return l[a] < l[b];}); for(int i: left_c){ if(r[i] < l_curr) sol += 2*(l_curr-r[i]); //2*1 l_curr = min(l_curr, l[i]); } for(int i: right_c){ if(l[i] > r_curr) sol += 2*(-r_curr+l[i]); r_curr = max(r_curr, r[i]); } return sol; }