#include <bits/stdc++.h>
#include "books.h"
using namespace std;
const long long inf = 1e18;
pair<long long, int> bfs(int from,
int to,
short mode,
const int &n,
const vector<pair<int, int> > &range){
vector<bool> used(n, false);
vector<long long> dist(n);
deque<int> q;
for(int i = 0; i < n; ++i)
dist[i] = inf;
q.push_back(from);
dist[from] = 0;
//cout << endl << from << " " << to << endl;
int l = from, r = from;
while(!q.empty()){
int u = q.front();
q.pop_front();
//cout << u << " - u" << endl;
//cout << dist[u] << " dist[u]" << endl;
if(mode == 1){
if(u <= to)
return {dist[to], to};
}
else if(mode == 2){
if(u >= to)
return {dist[to], to};
}
if(used[u])
continue;
used[u] = true;
r = max(r, u);
l = min(l, u);
if(range[u].first < l){
for(int i = range[u].first; i < l; ++i){
if(used[i])
continue;
q.push_front(i);
dist[i] = dist[u];
}
l = range[u].first;
}
if(range[u].second > r){
for(int i = r + 1; i <= range[i].second; ++i){
if(used[i])
continue;
q.push_front(i);
dist[i] = dist[u];
}
r = range[u].second;
}
if(range[u].second + 1 < n && dist[range[u].first + 1] > dist[u] + 1){
dist[range[u].second + 1] = dist[u] + 1;
q.push_back(range[u].second + 1);
}
if(range[u].first - 1 >= 0 && dist[range[u].first - 1] > dist[u] + 1){
dist[range[u].first - 1] = dist[u] + 1;
q.push_back(range[u].first - 1);
}
}
cout << "returning bullshit" << endl;
return {-1, -1};
}
long long minimum_walk(vector<int> p, int s) {
int n = (int)p.size();
vector<int> rev(n);
vector<pair<int, int> > range(n);
long long ans = 0;
for(int i = 0; i < n; ++i){
rev[p[i]] = i;
range[i] = {i, i};
}
int l = s, r = s;
for(int i = 0; i < n; ++i){
if(p[i] != i){
l = min(l, i);
r = max(r, i);
}
}
for(int i = 0; i < n; ++i){
if(p[i] != i){
vector<int> cycle;
int v = i;
do{
ans += abs(p[v] - v);
cycle.push_back(v);
int prev = v;
v = p[v];
p[prev] = prev;
}
while(v != i);
int l_cycle = cycle[0], r_cycle = cycle[0];
for(int x: cycle){
l_cycle = min(l_cycle, x);
r_cycle = max(r_cycle, x);
}
for(int x: cycle)
range[x] = {l_cycle, r_cycle};
}
}
pair<long long, int> l_ans = bfs(s, l, 1, n, range);
pair<long long, int> r_ans = bfs(s, r, 2, n, range);
if(l_ans < r_ans){
ans += l_ans.first + r_ans.first + bfs(l_ans.second, r, 2, n, range).first;
}
else{
ans += r_ans.first + l_ans.first + bfs(r_ans.second, l, 1, n, range).first;
}
return ans;
}
