#include "books.h"
#include<bits/stdc++.h>
using namespace std;
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ll long long
#define ordered_set tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>
#define fall(i,a,b) for(int i=a;i<=b;i++)
#define rfall(i,a,b) for(int i=a;i>=b;i--)
#define pb push_back
#define all(x) x.begin(),x.end()
#define sz(x) (int)x.size()
const ll inf=1e17;
long long minimum_walk(std::vector<int> p, int s){
int n=sz(p);
ll ans=inf,cost=0,cur=0;
int lef=0,ri=0;
fall(i,0,n-1){
int r=i,j=i;
while(j<=r){
r=max(r,p[j]); j++;
}
if(i<=s && r>=s) lef=i,ri=r;
i=r;
}
ordered_set st;
int ad=1,l=lef;
rfall(i,lef-1,0){
if(l<=i) continue;
int j=i;
l=i;
while(j>=l){
l=min(l,p[j]); j--;
}
if(l==i){
ad+=2;
continue;
}
cost+=ad; ad=0;
st.clear();
rfall(j,i,l+1){
st.insert(p[j]);
cost+=st.order_of_key(j);
}
st.clear();
fall(j,l,i-1){
st.insert(p[j]);
cost+=sz(st)-st.order_of_key(j+1);
}
ad++;
cost++;
}
ad=1;
int r=ri;
fall(i,ri+1,n-1){
if(r>=i) continue;
r=i;
int j=i;
while(j<=r){
r=max(r,p[j]);
j++;
}
if(r==i){
ad+=2;
continue;
}
cost+=ad; ad=0;
st.clear();
fall(j,i,r-1){
st.insert(p[j]);
cost+=sz(st)-st.order_of_key(j+1);
}
st.clear();
rfall(j,r,i+1){
st.insert(p[j]);
cost+=st.order_of_key(j);
}
ad++;
cost++;
}
fall(i,s,ri){
vector<int> volta(n);
st.clear();
cur=0;
fall(j,s,i-1){
st.insert(p[j]);
int val=sz(st)-st.order_of_key(j+1);
if(!val) cur++;
}
if(i==ri) cur=0;
st.clear();
rfall(j,i,lef+1){
st.insert(p[j]);
int val=st.order_of_key(j);
cur+=max(1,val);
if(val>=2) volta[j]=1;
}
st.clear();
if(i==ri){
fall(j,s,i-1){
st.insert(p[j]);
int val=sz(st)-st.order_of_key(j+1);
cur+=max(1,val);
}
st.clear();
int mx=s;
fall(j,lef,s-1) mx=max(mx,p[j]);
fall(i,s+1,mx) if(!volta[i]) cur++;
fall(j,lef,mx-1){
if(j<s) st.insert(p[j]);
cur+=sz(st)-st.order_of_key(j+1);
}
ans=min(ans,cur+cost);
continue;
}
fall(j,lef,ri-1){
st.insert(p[j]);
int val=sz(st)-st.order_of_key(j+1);
cur+=max(1,val);
}
int mn=s;
fall(j,i+1,ri) mn=min(mn,p[j]);
st.clear();
rfall(j,ri,mn+1){
if(j>i) st.insert(p[j]);
int val=st.order_of_key(j);
cur+=max(1,val);
}
cur+=s-mn;
ans=min(ans,cost+cur);
}
rfall(i,s,lef){ //TROCAR!
vector<int> volta(n);
st.clear();
cur=0;
rfall(j,s,i+1){
st.insert(p[j]);
int val=st.order_of_key(j);
if(val==0) cur++;
}
if(i==lef) cur=0;
st.clear();
fall(j,i,ri-1){
st.insert(p[j]);
int val=sz(st)-st.order_of_key(j+1);
cur+=max(1,val);
if(cur>=2) volta[j]=1;
}
st.clear();
if(i==lef){
rfall(j,s,i+1){
st.insert(p[j]);
int val=st.order_of_key(j);
cur+=max(1,val);
}
st.clear();
int mn=s;
fall(j,s+1,ri) mn=min(mn,p[j]);
rfall(j,ri,mn+1){
if(j>s) st.insert(p[j]);
int val=st.order_of_key(j);
cur+=max(1,val);
}
fall(j,mn,s-1) if(!volta[j]) cur++;
ans=min(ans,cur+cost);
continue;
}
rfall(j,ri,lef+1){
st.insert(p[j]);
int val=st.order_of_key(j);
cur+=max(1,val);
}
int mx=s;
fall(j,lef,i-1) mx=max(mx,p[j]);
st.clear();
fall(j,lef,mx-1){
if(j<i) st.insert(p[j]);
int val=sz(st)-st.order_of_key(j+1);
cur+=max(1,val);
}
cur+=mx-s;
ans=min(ans,cost+cur);
}
return ans;
}
