#include "books.h"
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
using ii = pair<int, int>;
map<vector<int>, int > nho;
map<int, vector<int> > rem;
int kc[120][4][5];
struct node {
int idx, s, hold;
node() {}
node(int _idx, int _s, int _hold) : idx(_idx), s(_s), hold(_hold) {}
bool operator < (const node &other) const {
if (idx != other.idx) return idx < other.idx;
if (s != other.s) return s < other.s;
return hold < other.hold;
}
};
/*
4 0
0 2 3 1
*/
long long minimum_walk(vector<int> p, int s) {
int n = p.size(), cc = 0;
if (1) {
vector<int> a(n);
iota(a.begin(), a.end(), 0);
do {
nho[a] = cc;
rem[cc] = a;
++cc;
for (int i = 0; i < n; i++) {
int T = a[i];
a[i] = n;
nho[a] = cc;
rem[cc] = a;
++cc;
a[i] = T;
}
} while (next_permutation(a.begin(), a.end()));
}
for (int i = 0; i < cc; i++) for (int j = 0; j < n; j++) for (int k = 0; k <= n; k++) kc[i][j][k] = INT_MAX;
set<pair<int, node> > q;
kc[nho[p]][s][n] = 0;
q.insert(pair<int, node>{0, node(nho[p], s, n)});
while (!q.empty()) {
auto [idx, s, hold] = q.begin()->se; q.erase(q.begin());
vector<int> cur = rem[idx];
if (1) {
vector<int> T = cur;
T[s] = hold;
int nex = nho[T];
if (kc[nex][s][cur[s]] > kc[idx][s][hold]) {
q.erase(pair<int, node>{kc[nex][s][cur[s]], node(nex, s, cur[s])});
kc[nex][s][cur[s]] = kc[idx][s][hold];
q.insert(pair<int, node>{kc[nex][s][cur[s]], node(nex, s, cur[s])});
}
}
for (int i = 0; i < n; i++)
if (kc[idx][i][hold] > kc[idx][s][hold] + abs(i-s)) {
q.erase(pair<int, node>{kc[idx][i][hold], node(idx, i, hold)});
kc[idx][i][hold] = kc[idx][s][hold] + abs(i-s);
q.insert(pair<int, node>{kc[idx][i][hold], node(idx, i, hold)});
}
}
return kc[0][s][n];
}
