#include "books.h"
#include "bits/stdc++.h"
using namespace std;
int n;
struct No_repetir{
vector<int> p;
int Inicio, Posici_n, Mano;
};
bool operator<(const No_repetir& a, const No_repetir& b){
if(a.p < b.p) return 1;
if(a.p > b.p) return 0;
if(a.Inicio < b.Inicio) return 1;
if(a.Inicio > b.Inicio) return 0;
if(a.Posici_n < b.Posici_n) return 1;
if(a.Posici_n > b.Posici_n) return 0;
return a.Mano < b.Mano;
}
map<No_repetir, long long> Programaci_n_din_mica_que_parece_recursi_n;
set<No_repetir> No;
long long Resolver(vector<int> p, int Inicio, int Posici_n, int Mano){
/*for(auto E: p) cerr<<E<<" ";
cerr<<"\n"<<Inicio<<" "<<Posici_n<<" "<<Mano<<"\n";*/
bool Bien = 1;
for(int i = 0; i < n and Bien; i++) if(p[i] != i) Bien = 0;
if(Bien) return abs(Posici_n - Inicio);
No_repetir Estado;
Estado.Inicio = Inicio;
Estado.Mano = Mano;
Estado.p = p;
Estado.Posici_n = Posici_n;
if(Programaci_n_din_mica_que_parece_recursi_n.count(Estado) == 1) return Programaci_n_din_mica_que_parece_recursi_n.count(Estado);
if(No.count(Estado) == 1) return 2222222222222222;
No.insert(Estado);
long long r = 2222222222222222;
if(Mano == -2){
for(int i = 0; i < n; i++){
swap(Mano, p[i]);
r = min(r, Resolver(p, Inicio, i, Mano) + abs(i - Posici_n));
swap(Mano, p[i]);
}
} else {
int Ir = Mano;
swap(p[Mano], Mano);
r = min(r, Resolver(p, Inicio, Ir, Mano) + abs(Ir - Posici_n));
}
No.erase(Estado);
if(No.empty()) return Programaci_n_din_mica_que_parece_recursi_n[Estado] = r;
else return r;
}
long long minimum_walk(vector<int> p, int s){
n = p.size();
return Resolver(p, s, 0, -2);
}
