#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];
}
}
// cerr << sol << '\n';
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);
}
}
// cerr << sol << " hello\n";
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;
l_currt = min(l_currt, l[cc[l_t]]);
if(r[cc[l_t]] > r_curr) break;
}
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;
r_currt = max(r_currt, r[cc[r_t]]);
if(l[cc[r_t]] < l_curr) break;
}
// cerr << l_t << ' ' << r_t << '\n';
if(endl && endr){
return sol + dst_l + dst_r;
}
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 = max(r_, r_currt);
l_curr = l[cc[r_]];
}
// cerr << sol << ' ' << l_curr << ' ' << r_curr << '\n';
}
return sol;
}
