#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;
}
