#include "books.h"
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
typedef long long ll;
struct state {
int hold, pos; string arr;
// vi hist;
state(int hold, int pos, string arr) : hold(hold), pos(pos), arr(arr) {}
const bool operator<(const state &other) const {
if (arr != other.arr) return arr < other.arr;
if (hold != other.hold) return hold < other.hold;
return pos < other.pos;
}
};
ll brute(vi p, int s) {
int n = p.size();
string target = ""; for (int i = 0; i < n; i++) target += 'a' + i;
string start = ""; for (auto i : p) start += 'a' + i;
state begin(-1, s, start);
queue<pair<int, state>> q; set<state> seen;
q.push({0, begin}); seen.insert(begin);
ll ans = -1;
while (!q.empty()) {
int moves = q.front().first; auto st = q.front().second;
q.pop();
// cout << "moves: " << moves << " arr: " << st.arr << " pos: " << st.pos << " hold: " << st.hold << "\n";
if (st.arr == target && st.pos == s && st.hold == -1) {
ans = moves;
// vi hist = st.hist;
// for (auto e : hist) {
// if (e == 0) {
// cout << "move right\n";
// } else if (e == 1) {
// cout << "swap and move right\n";
// } else if (e == 2) {
// cout << "move left\n";
// } else if (e == 3) {
// cout << "swap and move left\n";
// }
// }
break;
}
if (st.pos < n-1) {
auto st1 = state(st.hold, st.pos+1, st.arr);
string ifswap = st.arr; int h2 = st.hold;
if (st.hold != -1) {
ifswap[st.pos] = 'a' + st.hold;
if (st.arr[st.pos] == '#') h2 = -1;
else h2 = st.arr[st.pos] - 'a';
} else {
ifswap[st.pos] = '#';
h2 = st.arr[st.pos] - 'a';
}
auto st2 = state(h2, st.pos+1, ifswap);
// st1.hist = st2.hist = st.hist;
// st1.hist.push_back(0); st2.hist.push_back(1);
if (!seen.count(st1)) seen.insert(st1), q.push({moves+1, st1});
if (!seen.count(st2)) seen.insert(st2), q.push({moves+1, st2});
}
if (st.pos > 0) {
auto st1 = state(st.hold, st.pos-1, st.arr);
string ifswap = st.arr; int h2 = st.hold;
if (st.hold != -1) {
ifswap[st.pos] = 'a' + st.hold;
if (st.arr[st.pos] == '#') h2 = -1;
else h2 = st.arr[st.pos] - 'a';
} else {
ifswap[st.pos] = '#';
h2 = st.arr[st.pos] - 'a';
}
auto st2 = state(h2, st.pos-1, ifswap);
// st1.hist = st2.hist = st.hist;
// st1.hist.push_back(2); st2.hist.push_back(3);
if (!seen.count(st1)) seen.insert(st1), q.push({moves+1, st1});
if (!seen.count(st2)) seen.insert(st2), q.push({moves+1, st2});
}
}
return ans;
}
ll minimum_walk(vi p, int s) {
return brute(p, s);
}
