#include "bits/extc++.h"
using namespace std;
template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
cerr << t;
((cerr << " | " << u), ...);
cerr << endl;
}
#ifdef DEBUG
#define dbg(...) \
cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]: "; \
dbgh(__VA_ARGS__)
#else
#define dbg(...)
#define cerr \
if (false) \
cerr
#endif
using ll = long long;
#define endl "\n"
#define long int64_t
#define sz(x) int(std::size(x))
struct State {
vector<int> arr;
int mpos, mbook;
bool operator<(const State& s) const {
return tie(arr, mpos, mbook) < tie(s.arr, s.mpos, s.mbook);
}
};
ll minimum_walk(vector<int> arr, int kv) {
int n = sz(arr);
set<State> vis;
queue<pair<int, State>> q;
auto push = [&](const State& u, int d) -> void {
if (!vis.insert(u).second) {
return;
}
q.emplace(d, u);
};
push({arr, kv, -1}, 0);
while (sz(q)) {
auto [d, u] = q.front();
q.pop();
if (is_sorted(begin(u.arr), end(u.arr)) && u.mbook == -1 &&
u.mpos == kv) {
return d;
}
for (int du : {-1, 1}) {
int npos = u.mpos + du;
if (!(0 <= npos && npos < n)) {
continue;
}
push({u.arr, npos, u.mbook}, d + 1);
}
swap(u.arr[u.mpos], u.mbook);
push(u, d);
}
assert(false);
}
