#include "books.h"
#include <bits/stdc++.h>
using namespace std;
map<pair<vector<int>,int>,int> mp;
map<pair<vector<int>,int>,bool> vis;
int n;
long long minimum_walk(vector<int> p, int s) {
n = p.size();
deque<pair<vector<int>,int>> q;
q.push_front({p,0});
mp[{p,0}] = 0;
while(q.size()){
auto tp = q.front();
q.pop_front();
if(vis[tp])continue;
vis[tp] = 1;
auto p = tp.first;
auto pos = tp.second;
int cost = mp[{p,pos}];
set<int> hand;
for(int i = -1;i<n;i++){
hand.insert(i);
}
for(auto u:p){
hand.erase(u);
}
int on_hand = *hand.begin();
if(pos + 1 != n && (!mp.count({p,pos+1}) || mp[{p,pos+1}] > cost + 1)){
q.push_back({p,pos+1});
mp[{p,pos+1}] = cost + 1;
}
if(pos - 1 != -1 && (!mp.count({p,pos-1}) || mp[{p,pos-1}] > cost + 1)){
q.push_back({p,pos-1});
mp[{p,pos-1}] = cost + 1;
}
swap(p[pos],on_hand);
if(!mp.count({p,pos}) || mp[{p,pos}] > cost){
q.push_front({p,pos});
mp[{p,pos}] = cost;
}
}
vector<int> v;
for(int i = 0;i<n;i++){
v.push_back(i);
}
return mp[{v,s}];
}
