#include "books.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define pll pair <ll,ll>
#define fi first
#define se second
#define MP make_pair
#define sz(a) (ll((a).size()))
#define BIT(mask,i) (((mask) >> (i))&1)
#define MASK(i) (1LL << (i))
const ll MAXN = 1e6+100;
ll cnt[MAXN];
bool in[MAXN];
pll rg[MAXN];
ll dist[MAXN];
long long minimum_walk(std::vector<int> p, int s) {
ll n = sz(p);
for (ll i = 0;i < sz(p);i ++){
if (p[i] > i){
cnt[i]++,cnt[p[i]]--;
}
}
for (ll i = 1;i < n;i ++)cnt[i] += cnt[i-1];
int l = n + 1,r = -1;
ll res=0;
for (int i = 0;i < n;i ++){
if (cnt[i]){
res += cnt[i] * 2 - 2;
l = min(l,i);
r = max(r,i+1);
}
}
l = min(l,s);
r = max(r,s);
res += (r-l)*2;
if (s&&cnt[s]&&cnt[s-1]){
for (ll i = 0;i < n; i ++){
if (!in[i]){
ll cur = i;
vector <ll> all;
while (!in[cur]){
all.push_back(cur);
in[cur] = 1;
cur = p[cur];
}
ll min1,max1;
min1=n+1,max1=-1;
for (auto x:all){
min1 = min(min1,x);
max1 = max(max1,x);
}
for (auto x:all)rg[x] = MP(min1,max1);
}
}
memset(in,0,sizeof in);
ll ptr = s;
while (cnt[ptr])ptr++;
vector <ll> q;
q.push_back(s);
set <ll> sus;
for (ll i = 0;i < n;i ++){
sus.insert(i);
}
sus.erase(s);
while (!q.empty()){
for (ll j = 0;j < sz(q);j ++){
ll x = q[j];
for (auto it = sus.lower_bound(rg[x].fi); it != sus.end() && (*it) <= rg[x].se;it = sus.erase(it)){
dist[*it] = dist[x];
q.push_back(*it);
}
}
vector <ll> tmp;
for (ll j = 0;j < sz(q);j ++){
ll x = q[j];
if (x + 1 < n && sus.find(x+1)!=sus.end()){
dist[x+1] = dist[x] + 1;
tmp.push_back(x+1);
sus.erase(x+1);
}
if (x-1>=0 && sus.find(x-1)!=sus.end()){
dist[x-1] = dist[x] + 1;
tmp.push_back(x-1);
sus.erase(x-1);
}
}
swap(q,tmp);
}
res+=dist[ptr]*2;
}
return res;
}
