#include "books.h"
#include <cmath>
#include <iostream>
#include <algorithm>
#include <set>
using namespace std;
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))
using ll = long long;
int const nmax = 1000000;
int perm[1 + nmax], seen[1 + nmax];
void markcycle(int node, int color, pair<int,int> &interval){
seen[node] = color;
interval.first = min(interval.first, node);
interval.second = max(interval.second, node);
if(seen[perm[node]] == 0)
markcycle(perm[node], color, interval);
}
int dist(pair<int,int> a, pair<int,int> b){
return max(0, min(a.first, b.first) - max(a.second, b.second));
}
long long minimum_walk(std::vector<int> p, int start) {
int n = p.size();
for(int i = 0; i < n; i++)
perm[i] = p[i];
pair<int,int> orig(start, start);
markcycle(start, 2, orig);
ll result = 0;
for(int i = 0; i < n; i++)
result += fabs(perm[i] - i);
vector<pair<int,int>> weak;
for(int i = 0; i < n; i++)
if(seen[i] == 0 && perm[i] != i) {
pair<int,int> newinterval;
markcycle(i, 1, newinterval);
weak.push_back(newinterval);
}
sort(weak.begin(), weak.end());
while(1 < weak.size()){
pair<int,int> st1 = weak.back();
weak.pop_back();
pair<int,int> st2 = weak.back();
weak.pop_back();
result += dist(st1, st2) * 2;
weak.push_back({min(st1.first, st2.first), max(st1.second, st2.second)});
}
set<int> destinations;
for(int i = 0; i < n; i++)
if(seen[i] == 1)
destinations.insert(i);
int bonus = nmax;
if(destinations.size() == 0)
bonus = 0;
for(int i = orig.first; i <= orig.second; i++){
set<int>::iterator it = destinations.lower_bound(i);
if(it != destinations.end())
bonus = min(bonus, (int)fabs(*it - i));
if(it != destinations.begin()) {
it--;
bonus = min(bonus, (int)fabs(*it - i));
}
}
return result + bonus * 2;
}
/*
4 0
0 2 3 1
10 4
1 0 2 3 4 5 6 7 9 8
5 2
1 0 2 4 3
5 1
3 0 2 1 4
6 2
5 1 2 3 4 0
*/
