#include "books.h"
#include <bits/stdc++.h>
//#define int long long
#define pb push_back
using namespace std;
// first n is permutation , n is index, n+1 is book in hand
int n;
map<vector<int>,int> dis;
void bfs(vector<int> s){
deque<vector<int>> q;
q.push_front(s);
dis[s]=0;
while (!q.empty()){
vector<int> v=q.front(),to;
q.pop_front();
// switch books
to=v;
to[v[n]]=v[n+1];
to[n+1]=v[v[n]];
if (dis.find(to)==dis.end()){
dis[to]=dis[v];
q.push_front(to);
}
// walk forward
if (v[n]+1<n){
to=v;
to[n]=v[n]+1;
if (dis.find(to)==dis.end()){
dis[to]=dis[v]+1;
q.push_back(to);
}
}
//walk backwards
if (v[n]-1>=0){
to=v;
to[n]=v[n]-1;
if (dis.find(to)==dis.end()){
dis[to]=dis[v]+1;
q.push_back(to);
}
}
}
}
long long minimum_walk(std::vector<int32_t> p, int32_t s) {
n=p.size();
vector<int> v;
for (int i=0;i<n;i++) v.pb(i);
v.pb(s);
v.pb(n);
bfs(v);
v=p;
v.pb(s);
v.pb(n);
return dis[v];
}
