#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); vector<int> cc(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]){ cc[v] = cyc-1; vis[v] = 1; l.back() = min(l.back(), v); r.back() = max(r.back(), v); sol += (ll)abs(p[v]-v); v = p[v]; } } int s_l = 0; for(; s_l<n && p[s_l] == s_l; s_l++); if(s_l == n){return 0;} int s_r = n-1; for(; s_r >= 0 && p[s_r] == s_r; s_r--); // cerr << cyc << '\n'; // cerr << sol << '\n'; // cerr << s_l << ' ' << s_r << '\n'; if(s < s_l){ sol += 2*abs(s-s_l);s = s_l;} else if(s > s_r){ sol += 2*abs(s-s_r);s = s_r;} ll l_curr = l[cc[s]]; ll r_curr = r[cc[s]]; ll l_ = s; ll r_ = s; while(l_curr > s_l && r_curr < s_r){ while(l_ > l_curr || r_ < r_curr){ if(l_ > l_curr){ l_--; l_curr = min(l[cc[l_]], l_curr); r_curr = max(r[cc[l_]], r_curr); } if(r_ < r_curr){ r_++; l_curr = min(l[cc[r_]], l_curr); r_curr = max(r[cc[r_]], r_curr); } } int l_t = l_; ll l_currt = l_curr; ll dst_l = 0; bool endl = 0; while(l_t>=s_l){ if(l_t == s_l){endl = 1; break;} l_t--; if(l_t < l_currt) dst_l+=2; if(r[cc[l_t]] > r_curr) break; l_currt = min(l_currt, l[cc[l_t]]); } int r_t = r_; ll r_currt = r_curr; ll dst_r = 0; bool endr = 0; while(r_t<=s_r){ if(r_t == s_r){endr = 1; break;} r_t++; if(r_t > r_currt) dst_r+=2; if(l[cc[r_t]] < l_curr) break; r_currt = max(r_currt, r[cc[r_t]]); } if(endl == endr){ return sol + dst_l + dst_r; // return 0; } assert(!endl && !endr); if(dst_l < dst_r){ sol += dst_l; l_ = l_t; l_curr = min(l_, l_currt); r_curr = r[cc[l_]]; } else{ sol += dst_r; r_ = r_t; r_curr = min(r_, r_currt); l_curr = l[cc[r_]]; } } return sol; // 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] >= s){ // 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; }