#include <bits/stdc++.h>
#define pii pair<int, int>
#define F first
#define S second
#include "books.h"
using namespace std;
const int MX = 1e6 + 100;
pii v[MX];
int mn[MX], mx[MX], tmpn[MX], tmpx[MX];
unordered_map<int, int> dp[MX];
int dfs(int l, int r, int a, int b) {
// cout << l << ' ' << r << ' ' << a << ' ' << b << endl;
if(l == a and r == b) return 0;
if(dp[l].find(r) != dp[l].end()) return dp[l][r];
if(l == a) return 2 + dfs(l, v[r + 1].S, a, b);
if(r == b) return 2 + dfs(v[l - 1].F, r, a, b);
int l1 = min(v[l - 1].F, l);
int r1 = max(v[l - 1].S, r);
int l2 = min(v[r + 1].F, l);
int r2 = max(v[r + 1].S, r);
return dp[l][r] = 2 + min(dfs(l1, r1, a, b), dfs(l2, r2, a, b));
}
long long minimum_walk(vector<int> p, int s) {
int x = 0, y = p.size() - 1;
while(x < s and p[x] == x) x ++;
while(y > s and p[y] == y) y --;
for(int i = x; i <= y; i ++) mn[i] = mx[i] = i;
for(int i = x; i <= y; i ++) {
mn[i] = min(mn[i], p[i]);
mx[i] = max(mx[i], p[i]);
mn[p[i]] = min(mn[p[i]], i);
mx[p[i]] = max(mx[p[i]], i);
}
long long sum = 0;
for(int i = x; i <= y; i ++) sum += abs(p[i] - i);
auto update = [&] (int p, int a) {
mn[p] = min(mn[p], mn[a]);
mx[p] = max(mx[p], mx[a]);
};
{
memcpy(tmpn, mn, sizeof(mn));
memcpy(tmpx, mx, sizeof(mx));
queue<int> a, b;
for(int i = s - 1; i >= x; i --) a.push(i);
for(int i = s + 1; i <= y; i ++) b.push(i);
for(int i = s; i <= y; i ++) {
while(1) {
if(a.size() and a.front() >= mn[i]) update(i, a.front()), a.pop();
else if(b.size() and b.front() <= mx[i]) update(i, b.front()), b.pop();
else break;
}
v[i] = {mn[i], mx[i]};
i = mx[i];
}
memcpy(mn, tmpn, sizeof(mn));
memcpy(mx, tmpx, sizeof(mx));
}
{
memcpy(tmpn, mn, sizeof(mn));
memcpy(tmpx, mx, sizeof(mx));
queue<int> a, b;
for(int i = s - 1; i >= x; i --) a.push(i);
for(int i = s + 1; i <= y; i ++) b.push(i);
for(int i = s; i >= x; i --) {
while(1) {
if(a.size() and a.front() >= mn[i]) update(i, a.front()), a.pop();
else if(b.size() and b.front() <= mx[i]) update(i, b.front()), b.pop();
else break;
}
v[i] = {mn[i], mx[i]};
i = mn[i];
}
memcpy(mn, tmpn, sizeof(mn));
memcpy(mx, tmpx, sizeof(mx));
}
for(int i = x; i <= y; i ++) {
// cout << i << ' ' << v[i].F << ' ' << v[i].S << endl;
}
// exit(0);
return sum + dfs(v[s].F, v[s].S, x, y);
}
