#include "books.h"
#define MAXN 1000005
#define LL long long
using namespace std;
int N, S, cyc = 1, eL, eR, 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);
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
int pt1 = Lcur, pt2 = Rcur;
while (pt1 >= Lcur || pt2 <= Rcur) {
if (pt1 >= Lcur) {
Lcur = min(Lcur, L[pt1]);
Rcur = max(Rcur, R[pt1]);
pt1--;
}
if (pt2 <= Rcur) {
Lcur = min(Lcur, L[pt2]);
Rcur = max(Rcur, R[pt2]);
pt2++;
}
}
//if one boundary is reached
if (Lcur == eL && Rcur == eR) {
break;
} else if (Lcur == eL) {
ans+=2;
Rcur++;
} else if (Rcur == eR) {
ans+=2;
Lcur--;
}
//test expand right Cost to go beyond
}
return(ans);
}
