// Oh damn! Suddenly you're free to fly...
#include<bits/stdc++.h>
#include "books.h"
#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 1e6 + 10, mod = 1e9 + 7, inf = 1e9 + 10;
int pr[maxn], L[maxn], R[maxn];
int cnt[maxn];
int fnd(int u){
return pr[u] < 0 ? u : pr[u] = fnd(pr[u]);
}
void mrg(int a, int b){
if( (a = fnd(a)) == (b = fnd(b)) )
return;
if(pr[a] > pr[b])
swap(a, b);
L[a] = min(L[a], L[b]);
R[a] = max(R[a], R[b]);
pr[a]+= pr[b];
pr[b] = a;
}
ll minimum_walk(vector<int> p, int s){
memset(pr, -1, sizeof pr);
iota(L, L + maxn, 0);
iota(R, R + maxn, 0);
int n = sz(p);
ll ans = 0;
for(int i = 0; i < n; i++){
int l = i, r = p[i];
if(l > r)
swap(l, r);
ans+= r-l;
mrg(l, r);
cnt[l]++, cnt[r]--;
}
int safar = 0, sum = 0;
for(int i = 0; i < n-1; i++){
sum+= cnt[i];
safar+= (sum == 0 ? 1 : 0);
}
int iter = 0;
int l = s, r = s;
while(true){
assert(++iter == 1);
while(true){
bool is = 0;
while(r < R[fnd(s)])
mrg(s, ++r), is = 1;
while(l > L[fnd(s)])
mrg(s, --l), is = 1;
if(!is)
break;
}
int d1 = 0, d2 = 0;
while(r < n && L[fnd(s)] <= L[fnd(r)]){
d2+= R[fnd(s)] < R[fnd(r)];
mrg(s, r);
r++;
}
while(l >= 0 && R[fnd(l)] <= R[fnd(s)]){
d1+= L[fnd(s)] > L[fnd(l)];
mrg(s, l);
l--;
}
if(l == -1 || r == n){
assert(l == -1 && r == n);
assert(d1 == 0);
assert(d2 == safar);
ans+= 2 * (d1 + d2);
break;
}
else{
ans+= 2 * min(d1 + 1, d2 + 1);
assert(fnd(l) == fnd(r));
mrg(s, l);
mrg(s, r);
}
}
for(int i = 0; i < s && p[i] == i; i++){
ans-= 2;
}
for(int i = n-1; i > s && p[i] == i; i--){
ans-= 2;
}
return ans;
}
