#include "books.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
long long minimum_walk(vector<int> p, int s){
int n = (int)p.size();
ll ans = 0;
vector<int> cycle(n, -1);
vector<int> cmi, cma;
int numCycles = 0;
for(int i = 0; i < n; i++){
if(cycle[i] == -1 && p[i] != i){
int mi = i, ma = i;
int j = i;
do
{
mi = min(mi, j);
ma = max(ma, j);
cycle[j] = numCycles;
ans += abs(j-p[j]);
j = p[j];
}while(j != i);
numCycles++;
cmi.push_back(mi);
cma.push_back(ma);
}
}
int mi = s, ma = s;
int l = s, r = s;
vector<bool> vis(numCycles);
bool over = true;
while(true){
int i = -1;
while(r <= ma){
if(cycle[r] != -1 && !vis[cycle[r]]){
i = r;
break;
}
else r++;
}
if(i == -1)
while(l >= mi){
if(cycle[l] != -1 && !vis[cycle[l]]){
i = l;
break;
}
else l--;
}
if(i == -1 && over){
int costL = 0, costR = 0;
int candL = -1, candR = -1;
int until = mi;
for(int j = l; j >= 0; j--){
if(j < until) costL += 2;
if(cycle[j] != -1){
until = min(until, cmi[cycle[j]]);
if(cma[cycle[j]] > ma){
candL = j;
break;
}
}
}
until = ma;
for(int j = r; j < n; j++){
if(j > until) costR += 2;
if(cycle[j] != -1){
until = max(until, cma[cycle[j]]);
if(cmi[cycle[j]] < mi){
candR = j;
break;
}
}
}
if(costL < costR) i = candL;
else i = candR;
if(i != -1) ans += min(costL, costR);
if(i == -1) over = false;
}
if(i == -1){
int oldR = r, oldL = l;
while(r < n){
if(cycle[r] != -1 && !vis[cycle[r]]){
i = r;
ans += 2*(r+1-oldR);
break;
}
r++;
}
if(i == -1)
while(l >= 0){
if(cycle[l] != -1 && !vis[cycle[l]]){
i = l;
ans += 2*(oldL+1-l);
break;
}
l--;
}
}
if(i == -1) break;
vis[cycle[i]] = true;
mi = min(mi, cmi[cycle[i]]);
ma = max(ma, cma[cycle[i]]);
}
return ans;
}
