#include "books.h"
#include <vector>
#include <algorithm>
#include <iostream>
#include <cassert>
#define pb push_back
#define le(v) ((int)v.size())
using namespace std;
typedef long long ll;
int dp(vector<int> p, int s, int end) {
if (is_sorted(p.begin(), p.end())) {
return abs(s - end);
} else {
int rez = 1e9;
for (int i = 0; i < le(p); i++) {
if (p[i] != i) {
int cur = abs(i - s);
vector<int> q = p;
int t = q[i];
vector<int> ind{i};
while (t != i) {
ind.pb(t);
t = q[t];
}
// for (int x : ind) {
// cout << x << " ";
// }
// cout << endl;
for (int i = 0; i < le(ind); i++) {
int j = (i + 1) % le(ind);
cur += abs(ind[i] - ind[j]);
}
sort(ind.begin(), ind.end());
for (int x : ind) {
q[x] = x;
}
cur += dp(q, i, end);
rez = min(rez, cur);
}
}
return rez;
}
}
ll minimum_walk(vector<int> p, int s) {
// return dp(p, s, s);
ll rez = 0;
int buf = -1;
while (!is_sorted(p.begin(), p.end())) {
// cout << buf << " " << s << endl;
// for (int x : p) {
// cout << x << " ";
// }
// cout << endl;
if (buf == s) {
swap(p[s], buf);
} else if (buf < s) {
swap(buf, p[s]);
}
if (buf == -1) {
bool ok = true;
for (int i = s; i < le(p); i++) {
if (p[i] != i) {
ok = false;
}
}
if (ok) {
s--;
rez++;
} else {
s++;
rez++;
}
} else {
if (buf < s) {
s--;
} else s++;
rez++;
}
}
rez += s;
return rez;
}
