#include "books.h"
#include <bits/stdc++.h>
#define MAX_N 1000000
using namespace std;
struct cikl{
int l, r;//Najlevlji i najdesnji
long long sum;//suma p_i-i na ciklusu.
};
long long aps(int a){
return a>0?a:-1*a;
}
vector<cikl> C;
int numcyc=0, numcom=0;//broj ciklova
int N;
long long ans=0;
bool mark[MAX_N];
long long minimum_walk(vector<int> p, int s){
//Ako je s=0 i n<1000
N=p.size();
while(N && p[N-1]==N-1){
N--;//Ovaj deo mi ionako ne treba
}
if(!N)return 0;
for(int i=0; i<N; ++i){
if(!mark[i]){
numcyc++;
cikl A;
A.l=A.r=i;
A.sum=0;
int cur=i;
do{
cur=p[cur];
if(cur>A.r)A.r=cur;
if(cur<A.l)A.l=cur;
A.sum+=aps(p[cur]-cur);
mark[cur]=1;
}while(i!=cur);
C.push_back(A);
//Ovako formiran niz ciklova je sortiran prema levom kraju--koji je uvek i
}
}
ans=0;
for(int i=0; i<numcyc; ++i){
//printf("C[%d]:%d %d %d;\n", i, C[i].l, C[i].r, C[i].sum);
}
int scom=0, lcom=0, rcom=0;
for(int i=0; i<numcyc; ++i){
ans+=C[i].sum;
if(C[i].l<=rcom){
//Mogu da ga uhvatim, i dalje sam u istoj komponenti
}
else{
if(s>=lcom && s<=rcom)//Menjam komponentu
scom=numcom;
numcom++;
lcom=C[i].l;
}
if(C[i].r>rcom)
rcom=C[i].r;
}
ans+=2*numcom;
ans+=scom<numcom-scom?scom:numcom-scom;
return ans;
}
