#include "books.h"
#include <cmath>
#include <iostream>
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 sumright[1 + nmax], sumleft[1 + nmax];
long long minimum_walk(std::vector<int> p, int start) {
int n = p.size();
ll result = 0;
for(int i = 0; i < n; i++){
result += fabs(p[i] - i);
if(i < p[i]){
sumright[i]++;
sumright[p[i]]--;
} else if(p[i] < i){
sumleft[i - 1]++;
if(0 <= p[i])
sumleft[p[i] - 1]--;
}
}
for(int i = 1; i < n; i++)
sumright[i] += sumright[i - 1];
for(int i = n - 1; 0 <= i; i--)
sumleft[i] += sumleft[i + 1];
int last = start;
for(int i = start; i < n; i++){
if(0 < sumright[i]){
if(start != last)
result += 2 * (i - 1 - last);
last = i;
}
}
last = start;
for(int i = start - 1; 0 <= i; i--){
if(0 < sumright[i]){
if(start != last)
result += 2 * (last - (i + 1));
last = i;
}
}
int bonus = nmax;
if(result == 0)
bonus = 0;
for(int i = 0; i < n; i++)
if(i != p[i])
bonus = min(bonus, (int)fabs(start - i));
return result + bonus * 2;
}
/*
10 0
0 2 1 3 4 5 6 7 9 8
5 1
3 0 2 1 4
6 2
5 1 2 3 4 0
*/
