#include "books.h"
#include "bits/stdc++.h"
using namespace std;
int col[1000010];
bool vis[1000010];
bool v[1000010];
int l[1000010], r[1000010];
int cmp[1000010];
void dfs(int x, int c) {
v[x] = true;
for(int i = l[x]; i <= r[x]; i++) {
cmp[i] = c;
if(col[i] != -1 && v[col[i]] == false) {
dfs(col[i], c);
}
}
}
long long minimum_walk(std::vector<int> p, int s) {
long long ans = 0;
int n = p.size();
for(int i = 0; i < n-1; i++) {
int go_left = 0;
int go_right = 0;
for(int j = 0; j <= i; j++) {
if(p[j] > i) {
++go_left;
}
}
for(int j = i + 1; j < n; j++) {
if(p[j] < i+1) {
++go_right;
}
}
assert(go_left == go_right);
ans += go_left + go_right;
}
memset(col, -1, sizeof col);
memset(v, false, sizeof v);
int id = 0;
for(int i = 0; i < n; i++) {
if(col[i] != -1 || p[i] == i) continue;
int cur = i;
++id;
l[id] = n;
r[id] = 0;
while(col[cur] == -1) {
l[id] = min(l[id], cur);
r[id] = max(r[id], cur);
col[cur] = id;
cur = p[cur];
}
}
memset(cmp, -1, sizeof cmp);
int c = 0;
for(int i = 1; i <= id; i++) {
if(v[i] == false) {
dfs(i, ++c);
}
}
id = c;
for(int i = 0; i < n; i++) {
col[i] = cmp[i];
}
int opt = 1e9;
for(int i = s; i < n; i++) {
memset(vis, false, sizeof vis);
int cnt = 0;
int add = abs(s - i);
for(int j = s; j <= i; j++) {
if(col[j] != -1) {
if(vis[col[j]] == false) ++cnt;
vis[col[j]] = true;
}
}
for(int j = s; j >= 0; j--) {
if(col[j] != -1) {
if(vis[col[j]] == false) ++cnt;
vis[col[j]] = true;
}
if(cnt == id) {
add += abs(s - j);
break;
}
}
if(cnt == id) {
opt = min(opt, 2 * add);
}
}
ans += opt;
return ans;
}
