#include <bits/stdc++.h>
#include "books.h"
using namespace std;
const int N = 7, F = 5040, INF = 1e9 + 5;
struct Item{
vector<int> arr;
int indx, hold;
bool operator < (const Item &sc) const{
if(arr == sc.arr){
if(indx == sc.indx) return hold < sc.hold;
else return indx < sc.indx;
}
else return arr < sc.arr;
}
};
map<Item, int> dist;
long long minimum_walk(vector<int> p, int s){
int n = p.size();
vector<int> v(n);
iota(v.begin(), v.end(), 0);
dist[{p, s, -1}] = 0;
priority_queue<pair<int, Item>> pq;
pq.push({0, {p, s, -1}});
while(!pq.empty()){
auto v = pq.top().second; pq.pop();
if(v.indx - 1 >= 0){
Item nxt = {v.arr, v.indx - 1, v.hold};
if(dist.find(nxt) == dist.end() || dist[v] + 1 < dist[nxt]){
dist[nxt] = dist[v] + 1;
pq.push({-dist[nxt], nxt});
}
}
if(v.indx + 1 < n){
Item nxt = {v.arr, v.indx + 1, v.hold};
if(dist.find(nxt) == dist.end() || dist[v] + 1 < dist[nxt]){
dist[nxt] = dist[v] + 1;
pq.push({-dist[nxt], nxt});
}
}
if(v.hold == -1){
if(v.arr[v.indx] != -1){
Item nxt = {v.arr, v.indx, v.arr[v.indx]};
nxt.arr[v.indx] = -1;
if(dist.find(nxt) == dist.end() || dist[v] < dist[nxt]){
dist[nxt] = dist[v];
pq.push({-dist[nxt], nxt});
}
}
}
if(v.hold != -1){
Item nxt = v;
swap(nxt.arr[nxt.indx], nxt.hold);
if(dist.find(nxt) == dist.end() || dist[v] < dist[nxt]){
dist[nxt] = dist[v];
pq.push({-dist[nxt], nxt});
}
}
}
vector<int> sorted(n);
iota(sorted.begin(), sorted.end(), 0);
return dist[{sorted, s, -1}];
}
