#include<bits/stdc++.h>
#include "books.h"
using namespace std;
using ll=long long;
const ll MAX_TAILLE=1000*1000+5,MAX_MEMO=1000+5,DECA=(1<<10),INFINI=1000*1000*1000;
ll nbVal,rep,posDeb,nbCompo,debInter,finInter,maxFin;
vector<ll> obj,listeCompo;
ll idCompo[MAX_TAILLE],finCompo[MAX_TAILLE],tailleCompo[MAX_TAILLE],debCompo[MAX_TAILLE];
ll arbreMin[2*DECA],arbreMax[2*DECA];
ll memo[MAX_MEMO][MAX_MEMO];
void DFS(ll pos) {
if (idCompo[pos]==0) {
idCompo[pos]=nbCompo;
tailleCompo[nbCompo]++;
DFS(obj[pos]);
}
}
ll calcMin(ll deb,ll fin) {
if (deb==fin) {
return arbreMin[deb];
}
if (deb%2==1) {
return min(arbreMin[deb],calcMin(deb+1,fin));
}
if (fin%2==0) {
return min(arbreMin[fin],calcMin(deb,fin-1));
}
return calcMin(deb/2,fin/2);
}
ll calcMax(ll deb,ll fin) {
if (deb==fin) {
return arbreMax[deb];
}
if (deb%2==1) {
return max(arbreMax[deb],calcMax(deb+1,fin));
}
if (fin%2==0) {
return max(arbreMax[fin],calcMax(deb,fin-1));
}
return calcMax(deb/2,fin/2);
}
ll dyna(ll deb,ll fin) {
if (deb<=debInter and fin>=finInter) {
return 0;
}
if (memo[deb][fin]!=-1) {
return memo[deb][fin];
}
memo[deb][fin]=INFINI;
if (fin<nbVal-1) {
if (calcMax(DECA+deb,DECA+fin)>fin) {
memo[deb][fin]=min(memo[deb][fin],dyna(deb,fin+1));
}
else {
memo[deb][fin]=min(memo[deb][fin],dyna(deb,fin+1)+2);
}
}
if (deb>0) {
if (calcMin(DECA+deb,DECA+fin)<deb) {
memo[deb][fin]=min(memo[deb][fin],dyna(deb-1,fin));
}
else {
memo[deb][fin]=min(memo[deb][fin],dyna(deb-1,fin)+2);
}
}
return memo[deb][fin];
}
ll minimum_walk(vector<int> p, int s) {
posDeb=s;
nbVal=p.size();
for (auto i:p) {
obj.push_back(i);
}
for (ll i=nbVal-1;i>=0;i--) {
if (idCompo[i]==0) {
nbCompo++;
DFS(i);
finCompo[nbCompo]=i;
}
debCompo[idCompo[i]]=i;
rep+=abs(i-obj[i]);
}
finInter=nbVal-1;
while (finInter>=0 and tailleCompo[idCompo[finInter]]==1) {
finInter--;
}
debInter=0;
while (debInter<=nbVal-1 and tailleCompo[idCompo[debInter]]==1) {
debInter++;
}
if (posDeb==-1) {
ll pos=0;
while (pos<finInter) {
maxFin=max(maxFin,finCompo[pos]);
if (maxFin==pos) {
rep+=2;
}
pos++;
}
return rep;
}
for (ll i=0;i<MAX_MEMO;i++) {
for (ll j=0;j<MAX_MEMO;j++) {
memo[i][j]=-1;
}
}
for (ll i=0;i<2*DECA;i++) {
arbreMin[i]=INFINI;
arbreMax[i]=-INFINI;
}
for (ll i=0;i<nbVal;i++) {
arbreMin[DECA+i]=debCompo[idCompo[i]];
arbreMax[DECA+i]=finCompo[idCompo[i]];
}
for (ll i=DECA-1;i>0;i--) {
arbreMin[i]=min(arbreMin[2*i],arbreMin[2*i+1]);
arbreMax[i]=max(arbreMax[2*i],arbreMax[2*i+1]);
}
return rep+dyna(posDeb,posDeb);
}
