//In the name of God
#include <bits/stdc++.h>
#include "books.h"
using namespace std;
typedef int ll;
typedef pair<ll, ll> pll;
const ll maxn = 1e6 + 100;
const ll mod = 1e9 + 7;
const ll inf = 1e9;
#define pb push_back
#define Mp make_pair
#define F first
#define S second
#define Sz(x) ll((x).size())
#define all(x) (x).begin(), (x).end()
#define lc (id << 1)
#define rc (lc | 1)
ll a[maxn], t, tt, c[maxn], rr[maxn];
ll b[maxn];
ll mn[maxn], mx[maxn], mnp[maxn], mxp[maxn];
bool vis[maxn];
vector<ll> vec, g[maxn], gp[maxn], gg[maxn];
vector<pll> v2;
ll seg[maxn << 2];
void bld(ll id, ll s, ll e){
if(e - s == 1){
seg[id] = b[s];
return;
}
ll mid = (s + e) >> 1;
bld(lc, s, mid);
bld(rc, mid, e);
seg[id] = max(seg[lc], seg[rc]);
}
ll get(ll id, ll s, ll e, ll l, ll r){
if(r <= s || e <= l) return 0;
if(l <= s && e <= r) return seg[id];
ll mid = (s + e) >> 1;
return max(get(lc, s, mid, l, r), get(rc, mid, e, l, r));
}
void dfs(ll v){
vis[v] = 1;
for(ll u : g[v]){
if(!vis[u]) dfs(u);
}
vec.pb(v);
}
void sfd(ll v){
vis[v] = 1;
c[v] = tt;
mnp[tt] = min(mnp[tt], mn[v]);
mxp[tt] = max(mxp[tt], mx[v]);
for(ll u : gp[v]){
if(!vis[u]) sfd(u);
}
}
ll solve(ll v, ll s){
if(mnp[v] > s || s > mxp[v]) return 0;
ll x = -1;
ll ans = 0;
ll i = 0;
for(ll u : gg[v]){
if(mnp[u] <= s && s <= mxp[u]) x = i;
ans += solve(u, s);
i++;
}
if(x == -1) return ans;
if(mnp[v] == -1){
return ans + Sz(gg[v]) - 1;
}
return ans + max(0, min(x, Sz(gg[v]) - x - 1)) + 1;
}
long long minimum_walk(vector<int> p, int s){
ll n = Sz(p);
ll l = 0;
while(l < n && p[l] == l) l++;
ll r = n;
while(r && p[r - 1] == r - 1) r--;
l = min(l, s);
r = max(r, s + 1);
mn[0] = -1;
mx[0] = n + 1;
t++;
long long ans = 0;
for(ll i = l; i < r; i++){
ans += abs(p[i] - i);
if(!vis[i]){
ll v = i;
mn[t] = inf;
mx[t] = -inf;
do{
vis[v] = 1;
mx[t] = max(mx[t], v);
mn[t] = min(mn[t], v);
v = p[v];
}while(v != i);
rr[mx[t]] = t;
b[mn[t]] = mx[t];
t++;
}
}
bld(1, 0, n);
for(ll i = 0; i < t; i++){
v2.pb(Mp(mn[i], i));
}
for(pll i : v2){
if(!vis[i.S]) continue;
mnp[tt] = i.F;
mxp[tt] = mx[i.S];
vis[i.S] = 0;
while(true){
ll x = get(1, 0, n, mnp[tt], mxp[tt] + 1);
if(x > mxp[tt]) mxp[tt] = x;
else break;
vis[rr[x]] = 0;
}
tt++;
}
vec.clear();
v2.clear();
ll root = -1;
for(ll i = 0; i < tt; i++){
if(mnp[i] == -1) root = i;
v2.pb(Mp(mnp[i], i));
}
sort(all(v2));
for(pll i : v2){
if(vec.empty()){
vec.pb(i.S);
continue;
}
while(mxp[vec.back()] < i.F) vec.pop_back();
gg[vec.back()].pb(i.S);
vec.pb(i.S);
}
ll xx = solve(root, s);
ans += 2 * xx;
return ans;
}
