#include "books.h"
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using pi = pair<int, 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});
}
}
cout << "\n";
return ans;
}
ll test(vi p, int s) {
int n = p.size();
ll ans = 0; for (int i = 0; i < n; i++) ans += abs(i-p[i]);
vi found(n, 0); vector<pi> ranges;
for (int i = 0; i < n; i++) {
if (found[i]) continue;
int L = i, R = i;
int x = p[i]; found[x] = 1;
while (x != i) L = min(L, x), R = max(R, x), x = p[x], found[x] = 1;
ranges.push_back({L, R});
}
sort(ranges.begin(), ranges.end());
vector<pi> r2;
for (auto [l, r] : ranges) {
if (r2.empty() || l > r2.back().second) r2.push_back({l, r});
else r2.back().second = max(r2.back().second, r);
}
while (!r2.empty() && r2.back().first == r2.back().second) r2.pop_back();
// for (auto [l, r] : r2) cout << l << " " << r << "\n";
for (int i = 1; i < r2.size(); i++) ans += 2LL * (r2[i].first - r2[i-1].second);
return ans;
}
ll minimum_walk(vi p, int s) {
return test(p, s);
// return brute(p, s);
// vector<int> perm(5); iota(perm.begin(), perm.end(), 0);
// do {
// int a = brute(perm, 0), b = test(perm, 0);
// if (a != b) {
// cout << "FAILED: on n = 5, s = 0, p = "; for (auto e : perm) cout << e << " "; cout << "\n";
// cout << "brute: " << a << " test: " << b << "\n";
// }
// } while (next_permutation(perm.begin(), perm.end()));
// return brute(p, s);
}
