//#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first
#define b second
#define endl '\n'
#include "books.h"
int ans=0;
int n;
vector<int> adj[1000001];
int vis[1000001];
pair<int,int> cot[1000001];
int par[1000001];
/*int find(int no){
if(par[no]==no){
return no;
}
par[no]=find(par[no]);
return par[no];
}*/
vector<int> ss;
void dfs(int no){
vis[no]=1;
ss.pb(no);
for(auto j:adj[no]){
if(vis[j]==0){
dfs(j);
}
}
}
//vector<int> adj2[1000001];
int ind[1000001];
pair<int,int> pp;
vector<pair<int,int>> tt;
vector<pair<int,int>> pre2[1000001];
vector<pair<int,int>> pre3[1000001];
//int dp[1001][1001];
pair<int,int> rr2[1000001];
pair<int,int> rr[1000001];
/*void dfs2(int no,int par=-1){
pp.a=min(pp.a,tt[no].a);
pp.b=max(pp.b,tt[no].b);
vis[no]=1;
for(auto j:adj2[no]){
if(vis[j]==0){
dfs2(j);
}
}
}*/
vector<int> kk[1000001];
int tree[4*1000001];
void update(int no,int l,int r,int i,int j){
if(l==r){
tree[no]=min(tree[no],j);
}
else{
int mid=(l+r)/2;
if(i<=mid){
update(no*2+1,l,mid,i,j);
}
else{
update(no*2+2,mid+1,r,i,j);
}
tree[no]=min(tree[no*2+1],tree[no*2+2]);
}
}
int query(int no,int l,int r,int aa,int bb){
if(r<aa or l>bb){
return n;
}
if(aa<=l and r<=bb){
return tree[no];
}
else{
int mid=(l+r)/2;
return min(query(no*2+1,l,mid,aa,bb),query(no*2+2,mid+1,r,aa,bb));
}
}
int tree2[4*1000001];
void update2(int no,int l,int r,int i,int j){
if(l==r){
tree2[no]=max(tree2[no],j);
}
else{
int mid=(l+r)/2;
if(i<=mid){
update2(no*2+1,l,mid,i,j);
}
else{
update2(no*2+2,mid+1,r,i,j);
}
tree2[no]=max(tree2[no*2+1],tree2[no*2+2]);
}
}
int query2(int no,int l,int r,int aa,int bb){
if(r<aa or l>bb){
return 0;
}
if(aa<=l and r<=bb){
return tree2[no];
}
else{
int mid=(l+r)/2;
return max(query2(no*2+1,l,mid,aa,bb),query2(no*2+2,mid+1,r,aa,bb));
}
}
long long minimum_walk(std::vector<int> p, int s) {
while(p.size()){
if(p.back()+1==p.size()){
p.pop_back();
}
else{
break;
}
}
n=p.size();
if(n==0){
return 0;
}
for(int i=0;i<n;i++){
adj[i].pb(p[i]);
}
//int co=0;
llo ans=0;
vector<vector<int>> zz5;
for(int i=0;i<n;i++){
if(vis[i]==0){
ss.clear();
dfs(i);
int mi=ss[0];
int ma=ss[0];
for(auto j:ss){
mi=min(mi,j);
ma=max(ma,j);
}
for(auto j:ss){
cot[j]={mi,ma};
}
int zz=tt.size();
for(auto j:ss){
ind[j]=tt.size();
}
rr2[tt.size()]={mi,ma};
tt.pb({mi,ma});
for(int j=0;j+1<ss.size();j++){
ans+=(llo)abs(ss[j]-ss[j+1]);
}
zz5.pb(ss);
ans+=(llo)(abs(ss[0]-ss.back()));
sort(ss.begin(),ss.end());
for(int j=0;j+1<ss.size();j++){
pre2[ss[j+1]].pb({ss[j],zz});
}
for(int j=0;j+1<ss.size();j++){
pre3[ss[j]].pb({ss[j+1],zz});
}
}
}
for(int i=0;i<4*n;i++){
tree[i]=4*n;
}
for(int i=0;i<n;i++){
for(auto j:pre2[i]){
int x=query(0,0,n-1,j.a,i-1);
rr2[j.b].a=min(rr2[j.b].a,x);
update(0,0,n-1,i,rr2[j.b].a);
}
}
for(int i=0;i<4*n;i++){
tree2[i]=0;
}
for(int i=n-1;i>=0;i--){
for(auto j:pre3[i]){
int x=query2(0,0,n-1,i+1,j.a);
rr2[j.b].b=max(rr2[j.b].b,x);
update2(0,0,n-1,i,rr2[j.b].b);
}
}
for(int i=0;i<tt.size();i++){
for(auto j:zz5[i]){
rr[j]=rr2[i];
}
}
pair<int,int> cur3={rr[s].a,rr[s].b};
while(cur3.a>0 or cur3.b<n-1){
if(cur3.b==n-1){
ans+=2;
cur3={rr[cur3.a-1].a,max(cur3.b,rr[cur3.a-1].b)};
continue;
}
else if(cur3.a==0){
ans+=2;
cur3={min(rr[cur3.b+1].a,cur3.a),rr[cur3.b+1].b};
continue;
}
else{
if(rr[cur3.a-1].b>cur3.b){
ans+=2;
cur3={rr[cur3.a-1].a,max(cur3.b,rr[cur3.a-1].b)};
continue;
}
else if(rr[cur3.b+1].a<cur3.a){
ans+=2;
cur3={min(rr[cur3.b+1].a,cur3.a),rr[cur3.b+1].b};
continue;
}
vector<pair<int,int>> aa;
vector<pair<int,int>> bb;
pair<int,int> cur4=cur3;
pair<int,int> cur5=cur3;
int st=0;
while(cur4.a>0 or cur5.b<n-1){
if(cur5.b==n-1){
st=1;
break;
}
if(cur4.a==0){
st=0;
break;
}
if(rr[cur4.a-1].b>cur3.b){
st=0;
break;
}
if(rr[cur5.b+1].a<cur3.a){
st=1;
break;
}
cur4={rr[cur4.a-1].a,max(cur4.b,rr[cur4.a-1].b)};
aa.pb(cur4);
cur5={min(rr[cur5.b+1].a,cur5.a),rr[cur5.b+1].b};
bb.pb(cur5);
}
/*if(cur5.b==n-1){
st=1;
}*/
/*while(cur5.b<n-1){
}*/
if(st==0){
cur3=aa.back();
ans+=(llo)2*aa.size();
}
else{
cur3=bb.back();
ans+=(llo)2*bb.size();
}
//cur3={rr[cur3.a-1].a,max(cur3.b,rr[cur3.a-1].b)};
}
}
return ans;
}
