#include "books.h"
#include<bits/stdc++.h>
using namespace std;
const int INF = 1e9;
int n;
int p[1000005];
int maxpref[1000005],minsuff[1000005];
bool br[1000005],br2[1000005];
long long minimum_walk(std::vector<int> cit_p, int s)
{
s++;
n = cit_p.size();
for(int i=1;i<=n;i++)
p[i] = cit_p[i-1]+1;
int ult=0,primu=n+1;
long long rez=0;
for(int i=1;i<=n;i++)
{
maxpref[i] = max(maxpref[i-1], p[i]);
if(p[i]!=i)
{
ult=i;
primu = min(primu, i);
}
rez += abs(p[i]-i);
}
minsuff[n+1] = n+1;
for(int i=n;i>0;i--)
minsuff[i] = min(minsuff[i+1], p[i]);
if(ult==0)
return 0;
ult = max(ult, s);
primu = min(primu, s);
for(int i=primu+1;i<=ult;i++)
if(maxpref[i-1]<i && minsuff[i]>=i)
br[i]=1;
for(int i=primu+1;i<=s;i++)
{
bool gasit=0;
for(int j=1;j<i;j++)
if(i<=p[j] && p[j]<=s)
gasit=1;
for(int j=i;j<=s;j++)
if(p[j]<i)
gasit=1;
if(!gasit)
br2[i]=1;
}
for(int i=s+1;i<=ult;i++)
{
bool gasit=0;
for(int j=i;j<=n;j++)
if(s<=p[j] && p[j]<i)
gasit=1;
for(int j=s;j<i;j++)
if(p[j]>=i)
gasit=1;
if(!gasit)
br2[i]=1;
}
int tole=s,tori=s;
while(tole-1>=1 && !br[tole])
tole--;
while(tori+1<=n && !br[tori+1])
tori++;
int tole2=s,tori2=s;
while(tole2-1>=1 && !br2[tole2])
tole2--;
while(tori2+1<=n && !br2[tori2+1])
tori2++;
//rez += 2*min(tori-tori2, tole2-tole);
int cntri2=0,cntri=0;
for(int i=s+1;i<=n;i++)
{
if(br2[i])
cntri2++;
if(br[i])
cntri++;
}
int cntle2=0,cntle=0;
for(int i=2;i<=s;i++)
{
if(br2[i])
cntle2++;
if(br[i])
cntle++;
}
int secvle=0,secvri=0;
for(int i=s+1;i<=n;i++)
{
if(p[i]!=i)
break;
secvri++;
}
for(int i=s-1;i>0;i--)
{
if(p[i]!=i)
break;
secvle++;
}
rez += min(cntle*2 + cntri2*2 - 2*secvle, cntri*2 + cntle2*2 - 2*secvri);
return rez;
}
