#include "books.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;
#define endl '\n'
#define F first
#define S second
#define all(x) (x).begin(),(x).end()
const int N = 1e6+5;
const ll INF = 2e18;
const int MOD = 1e9+7;
int l[N],r[N],par[N];
int find(int x){
return (par[x] == x) ? x : par[x] = find(par[x]);
}
void join(int x, int y){
x = find(x);
y = find(y);
if(x==y)return;
par[y] = x;
l[x] = min(l[x],l[y]);
r[x] = max(r[x],r[y]);
}
long long minimum_walk(vector<int> p, int s) {
int i,j,n = p.size();
ll ans = 0;
bool ok[n] = {};
int cnt = 0;
for(i=0;i<n;i++){
if(p[i] == i){
ok[i] = true;
cnt++;
}
l[i] = i,r[i] = i,par[i] = i;
}
i = 0;
while(cnt < n){
while(ok[i]){
i++;
//ans++;
}
int fin = i;
ans += abs(p[i] - i);
i = p[i];
ok[i] = true;
cnt++;
while(i != fin){
join(i,fin);
ans += abs(p[i] - i);
i = p[i];
ok[i] = true;
cnt++;
}
//cout<<cnt<<" "<<ans<<" "<<i<<endl;
}
int low=s,high=s;
i=s,j=s;
while(i>0 || j<n-1){
int curr;
if(i >= 0)
curr = find(i);
else
curr = find(j);
bool ok = 0;
low = min(low,l[curr]);
while(i > low){
i--;
ok = 1;
join(curr,i);
low = min(low,l[curr]);
}
high = max(high,r[curr]);
while(j < high){
j++;
ok = 1;
join(curr,j);
high = max(high,r[curr]);
}
if(!ok){
i--;
while(i>=0 && i==par[i])
i--;
j++;
while(j<n && j==par[j])
j++;
if(i==-1 && j==n)break;
if(i==-1 || j<n && low-i > j-high){
/// go right (high)
int nhigh = max(high,r[find(j)]);
int nlow = min(low,l[find(j)]);
int jj = j;
while(j < nhigh){
j++;
nhigh = max(nhigh,r[find(j)]);
nlow = min(nlow,l[find(j)]);
}
if(i!=-1 && nlow == low){
ans += (low-i)*2;
join(curr,i);
j = high;
}
else{
j = jj;
ans += (j-high)*2;
join(curr,j);
i = low;
}
}
else{
assert(j==n || i>=0 && low-i < j-high);
/// go left (low)
int nhigh = max(high,r[find(i)]);
int nlow = min(low,l[find(i)]);
int ii = i;
while(i > nlow){
i--;
nhigh = max(nhigh,r[find(i)]);
nlow = min(nlow,l[find(i)]);
}
if(j!=n && nhigh == high){
ans += (j-high)*2;
join(curr,j);
i = low;
}
else{
i = ii;
ans += (low-i)*2;
join(curr,i);
j = high;
}
}
}
}
return ans;
}
