#include <bits/stdc++.h>
#include "books.h"
using namespace std;
long long minimum_walk(vector<int> p, int s) {
long long ans = 0, N = p.size();
for (int i=0; i<N; i++) ans += abs(p[i]-i);
int last_ordered = N, first_unordered = -1;
for (int i = 0; i < s; i++) {
if (p[i] != i) break;
first_unordered = i;
}
for (int i = N-1; i > s; i--) {
if (p[i] != i) break;
last_ordered = i;
}
if (last_ordered == 0) return 0;
auto expand = [&](int start, int l, int r) -> pair<int, int> {
int m_l = l, m_r = r;
m_l = min(start, m_l); m_r = max(start, m_r);
//cout << "start expand " << start << " " << l << " " << r << endl;
do {
//cout << "curr max " << m_l << " " << m_r << endl;
for (; r <= m_r; r++) {
m_r = max(m_r, p[r]);
m_l = min(m_l, p[r]);
}
r--;
for (; l >= m_l; l--) {
m_r = max(m_r, p[l]);
m_l = min(m_l, p[l]);
}
l++;
//cout << "expanded " << l << " " << r << endl;
}
while (m_l != l || m_r != r);
return {l, r};
};
int curr_seg_left = s, curr_seg_right = s;
tie(curr_seg_left, curr_seg_right) = expand(s, s, s);
//cout<< "initial s segment" << curr_seg_left << " " << curr_seg_right << endl;
while (1) {
//cout << "working with " << curr_seg_left << " " << curr_seg_right << endl;
int ns_left = 0, ns_right = 0;
int superseg_left = -1, superseg_right = -1;
// count segments to the left
while (curr_seg_left > first_unordered+1) {
//cout << "expanding left" << endl;
auto [new_left, new_right] = expand(curr_seg_left-1, curr_seg_left, curr_seg_right);
if (new_right > curr_seg_right) {
// found superseg
superseg_left = new_left;
superseg_right = new_right;
//...
break;
}
else {
ns_left++;
curr_seg_left = new_left;
}
}
// count segments to the right
while (curr_seg_right < last_ordered-1) {
//cout << "expanding right" << endl;
auto [new_left, new_right] = expand(curr_seg_right+1, curr_seg_left, curr_seg_right);
if (new_left < curr_seg_left) {
// found superseg
assert(superseg_left == new_left);
assert(superseg_right == new_right);
// ...
break;
}
else {
ns_right++;
curr_seg_right = new_right;
}
}
// check minim or exit
//cout << "segments found " << ns_left << " " << ns_right << endl;
if (superseg_left != -1) {
//assert(superseg_right != curr_seg_right);
ans += (min(ns_left, ns_right)+1)*2;
curr_seg_left = superseg_left;
curr_seg_right = superseg_right;
}
else {
ans += (ns_left+ns_right)*2;
return ans;
}
}
return ans;
}
