#include "books.h"
#include<bits/stdc++.h>
using namespace std;
#define sz(v) ((int)(v).size())
typedef long long lint;
int b,n,sz,cnt;
int v[1000002],rev[1000002];
vector<int>go;
lint ans=0;
void dfs(int p,int q)
{
if(b==-1)
{
ans+=p;
return ;
}
if(q==b)
{
if(p==b)
{
int tmp=go[p];
go[p]=q;
while(b-1>=0 && go[b-1]==b-1)b--;
b--;
dfs(p,tmp);
}
else
{
ans+=abs(p-b);
dfs(b,q);
}
return ;
}
if(go[p]==p)
{
ans++;
if(rev[b]>p)dfs(p+1,q);
else dfs(p-1,q);
}
else
{
int tmp=go[p];
go[p]=q;
if(tmp==b)
{
dfs(p,tmp);
return ;
}
ans++;
if(rev[b]>p)dfs(p+1,tmp);
else dfs(p-1,tmp);
}
}
lint minimum_walk(vector<int> p, int s) {
n=sz(p);
go=p;
for(int i=0;i<n;i++)rev[go[i]]=i;
b=n;
while(b-1>=0 && go[b-1]==b-1)b--;
b--;
dfs(0,-1);
return ans;
}
