#include<bits/stdc++.h>
#include "books.h"
using namespace std;
#define ff first
#define ss second
#define all(x) x.begin(), x.end()
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
template<typename T>
using matrix = vector<vector<T>>;
const int INF = 1e9;
long long minimum_walk(std::vector<int> p, int s) {
int n = p.size();
ll resp =0;
for(int i = 0; i < n; i++){
resp+=abs(i-p[i]);
}
vector<pii> crange(n);
vector<int> cycle(n), check(n);
auto dfs = [&](int id, int cid, auto dfs)->int{
cycle[id] = cid;
check[id] = 1;
if(check[p[id]])
return id;
return max(id,dfs(p[id],cid,dfs));
};
vector<int> isgood(n);
vector<pii> cycles;
for(int i = 0; i < n; i++){
if(!check[i]){
int r = dfs(i,i,dfs);
crange[i] = {i,r};
isgood[i] = cycles.empty() || cycles.back().ss < r;
if(r-i && isgood[i]){
if(cycles.size() && cycles.back().ss > i){
int l = cycles.back().ff;
cycles.pop_back();
cycles.push_back({l,r});
} else {
cycles.push_back({i,r});
}
}
}
}
for(int i = 0; i < (int)cycles.size()-1; i++){
resp+= 2*(cycles[i+1].ff-cycles[i].ss);
}
if(cycles.empty())
return resp;
if(s < cycles[0].ff || s > cycles.back().ss){
resp+=max(cycles[0].ff-s, s-cycles.back().ss)*2;
return resp;
}
matrix<pii> g(n);
for(int i = 0; i < n-1; i++){
int cur = cycle[i];
g[cur].push_back({cycle[i+1],2});
g[cycle[i+1]].push_back({cur,2});
}
vector<int> st;
for(int i = 0; i < n; i++){
if(st.empty()){
st.push_back(i);
goto END;
}
g[st.back()].push_back({cycle[i],0});
if(cycle[i]!=i)
goto END;
while(!st.empty() && crange[st.back()].ss < crange[i].ss){
g[i].push_back({st.back(),0});
st.pop_back();
}
st.push_back(i);
END:
if(i == crange[st.back()].ss)
st.pop_back();
}
priority_queue<pii,vector<pii>,greater<pii>> pq;
vector<int> dist(n,INF);
pq.push({0,cycle[s]});
dist[cycle[s]] = 0;
while(!pq.empty()){
int cur = pq.top().ss, curp = pq.top().ff;
pq.pop();
if(curp> dist[cur])
continue;
for(auto [viz,vizp] : g[cur]){
if(dist[viz] > vizp+dist[cur]){
dist[viz]= vizp+dist[cur];
pq.push({dist[viz],viz});
}
}
}
int add = INF;
for(int i = 0; i < n; i++){
if(isgood[i])
add = min(add,dist[i]);
}
resp+=add;
return resp;
}
