#include "books.h"
#include <bits/stdc++.h>
using namespace std;
long long minimum_walk(vector<int>P,int S){
assert(S==0);
int N=P.size();
map<pair<vector<int>,pair<int,int>>,int>mp;
priority_queue<pair<int,pair<vector<int>,pair<int,int>>>,vector<pair<int,pair<vector<int>,pair<int,int>>>>,greater<pair<int,pair<vector<int>,pair<int,int>>>>>pq;
pq.push({0,{P,{0,-1}}});
while(!pq.empty()){
vector<int>v=pq.top().second.first;
int pos=pq.top().second.second.first;
int hold=pq.top().second.second.second;
int dis=pq.top().first;
pq.pop();
if(mp.find({v,{pos,hold}})==mp.end()){
mp[{v,{pos,hold}}]=dis;
swap(v[pos],hold);
pq.push({dis,{v,{pos,hold}}});
swap(v[pos],hold);
if(pos){
pq.push({dis+1,{v,{pos-1,hold}}});
}
if(pos!=N-1){
pq.push({dis+1,{v,{pos+1,hold}}});
}
}
}
vector<int>K;
for(int i=0;i<N;i++){
K.push_back(i);
}
return mp[{K,{0,-1}}];
}
