#include "books.h"
#include<iostream>
#define MAXN 1000005
#define LL long long
using namespace std;
int N, S, cyc = 1, eL=N+1, eR=0, Lcur, Rcur;
int L[MAXN], R[MAXN], P[MAXN], C[MAXN];
bool vis[MAXN];
LL ans;
LL minimum_walk(vector<int> p, int s) {
N = p.size(), S = s+1, Lcur = S, Rcur = S;
for (int i=0; i<N; i++) {
P[i+1]=p[i]+1; //1 index
ans += (LL) max(p[i] - i, i - p[i]);
}
for (int i=1; i<=N; i++) {
int cur = P[i];
L[cyc] = 1<<30, R[cyc] = -1<<30;
while (!vis[cur]) {
L[cyc] = min(L[cyc], cur);
R[cyc] = max(R[cyc], cur);
C[cur] = cyc;
vis[cur] = true;
cur = P[cur];
}
cyc++;
}
for (int i=1; i<=N; i++) {
if (P[i] != i) {
eL = i;
break;
}
}
for (int i=N; i>=1; i--) {
if (P[i] != i) {
eR = i;
break;
}
}
while (Lcur > eL || Rcur < eR) {
//expand left and right as much as frontier allows
//printf("%d %d %d %d\n",Lcur, Rcur, eL, eR);
int pt1 = Lcur, pt2 = Rcur;
while (pt1 >= Lcur || pt2 <= Rcur) {
if (pt1 >= Lcur) {
Lcur = min(Lcur, L[C[pt1]]);
Rcur = max(Rcur, R[C[pt1]]);
pt1--;
}
if (pt2 <= Rcur) {
Lcur = min(Lcur, L[C[pt2]]);
Rcur = max(Rcur, R[C[pt2]]);
pt2++;
}
}
//if one boundary is reached
//printf("After: %d %d\n",Lcur, Rcur);
if (Lcur <= eL && Rcur >= eR) {
break;
} else if (Lcur <= eL) {
ans+=2;
Rcur++;
} else if (Rcur >= eR) {
ans+=2;
Lcur--;
} else {
//test expand right Cost to go beyond
int tmpL = Lcur + 1, tmpR = Rcur + 1, ptL = Lcur, ptR = Rcur;
int Lcost = 1, Rcost = 1;
bool root = true;
//check R cost:
while (ptR < eR) {
if (ptR > tmpR) {tmpR = ptR, Rcost++;}
tmpR = max(tmpR, R[C[ptR]]);
if (L[C[ptR]] < Lcur) {
root = false;
break;
}
ptR++;
}
//check L cost:
while (ptL > eL) {
if (ptL < tmpL) {tmpL = ptL, Lcost++;}
tmpL = min(tmpL, L[C[ptL]]);
if (R[C[ptL]] > Rcur) {
root = false;
break;
}
ptL--;
}
if (root) {
ans+=2*(Lcost + Rcost);
break;
} else if (Lcost > Rcost) {
Rcur = ptR, Lcur = L[C[ptR]];
ans+=2*Rcost;
} else {
Lcur = ptL, Rcur = R[C[ptL]];
ans+=2*Lcost;
}
}
}
return(ans);
}
