#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);
priority_queue<pair<int, state>, vector<pair<int, state>>, greater<pair<int, state>>> q; set<state> seen;
q.push({0, begin}); seen.insert(begin);
ll ans = -1;
while (!q.empty()) {
int moves = q.top().first; auto st = q.top().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 << "R";
} else if (e == 1) {
cout << "L";
} else if (e == 2) {
cout << "S";
}
}
break;
}
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, ifswap);
st2.hist = st.hist; st2.hist.push_back(2);
if (!seen.count(st2)) seen.insert(st2), q.push({moves, st2});
if (st.pos < n-1) {
auto st1 = state(st.hold, st.pos+1, st.arr);
st1.hist = st.hist; st1.hist.push_back(0);
if (!seen.count(st1)) seen.insert(st1), q.push({moves+1, st1});
}
if (st.pos > 0) {
auto st1 = state(st.hold, st.pos-1, st.arr);
st1.hist = st.hist; st1.hist.push_back(1);
if (!seen.count(st1)) seen.insert(st1), q.push({moves+1, st1});
}
}
return ans;
}
ll minimum_walk(vi p, int s) {
// return brute(p, s);
int n = p.size();
vi sp = p; sort(sp.begin(), sp.end());
ll ans = 0; int held = -1, pos = 0;
bool forward = true;
while (sp != p || pos != s) {
if (forward) {
if (pos == held || (pos < p[pos])) {
// cout << "S";
swap(held, p[pos]);
}
if (pos == n-1 || (held != -1 && held < pos)) {forward = false; continue;}
pos++; ans++;
// cout << "R";
} else {
if (pos == held || (p[pos] < pos)) {
swap(held, p[pos]);
}
if (pos == 0 ||(held != -1 && held > pos)) {forward = true; continue;}
pos--; ans++;
// cout << "L";
}
}
// cout << "\n";
return ans;
}
