#include"books.h"
#include <vector>
#include<bits/stdc++.h>
const int maxn=1000000+10;
using namespace std;
int vis[maxn],visa[maxn],av[maxn],tr[maxn];
int n;
long long mainres=0,last=0;
vector<pair<int,pair<int,int>>>alle;
struct dsu{
int par[maxn];
dsu(){
for(int i=0;i<maxn;i++){
par[i]=i;
}
}
void clear(){
for(int i=0;i<maxn;i++){
par[i]=i;
}
}
int root(int u){
if(u==par[u]){
return u;
}
return par[u]=root(par[u]);
}
int con(int u,int v){
u=root(u);
v=root(v);
if(u==v){
return 0;
}
par[u]=v;
return 1;
}
}ds;
void mst(){
ds.clear();
sort(alle.begin(),alle.end());
for(int i=0;i<(int)alle.size();i++){
if(ds.con(alle[i].second.first,alle[i].second.second)){
mainres+=alle[i].first;
}
}
}
long long minimum_walk(std::vector<int> p, int s){
mainres=0;
n=p.size();
for(int i=0;i<=n;i++){
vis[i]=visa[i]=0;
}
last=0;
int cnt1=0;
for(int i=0;i<n;i++){
if(p[i]>i){
cnt1++;
visa[p[i]]=1;
}
if(visa[i]){
cnt1--;
}
mainres+=cnt1*2;
if(cnt1!=0){
last=i+1;
}
}
for(int i=0;i<n;i++){
if(i==p[i]){
continue;
}
if(vis[i]==0){
//mainres+=2;
int now=i;
do{
av[now]=i;
vis[now]=1;
tr[i]=max(tr[i],now);
now=p[now];
}while(now!=i);
}
}
last=-1;
alle.clear();
int mx=0;
for(int i=0;i<n;i++){
if(i==p[i]){
continue;
}
if(i<=mx){
mx=max(mx,tr[i]);
}else{
mainres+=(i-mx)*2;
mx=max(mx,tr[i]);
}
}
return mainres;
}
