#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
struct State {
vector<pair<int, int>> swaps;
int moves;
};
bool check_valid(State &state, vector<int> &initial) {
vector<int> arrangement = initial;
for (auto &el : state.swaps) {
swap(arrangement[el.first], arrangement[el.second]);
}
bool valid = true;
for (int i = 0; i < n; i++) {
valid = valid && (abs(arrangement[2*i]) == abs(arrangement[2*i+1])) && (arrangement[2*i] < 0 && arrangement[2*i+1] > 0);
}
return valid;
}
// left shoe if s[i] < 0
// right shoe if s[i] > 0
ll count_swaps(vector<int> s) {
n = s.size() / 2;
int minimum = 0;
queue<State> q;
State best;
q.push(State{{}, 0});
while (!q.empty()) {
State cur = q.front();
q.pop();
if (check_valid(cur, s)) {
minimum = cur.moves;
best = cur;
break;
}
for (int i = 1; i < 2*n; i++) {
for (int j = i-1; j < i+2; j++) {
if (i == j) continue;
vector<pair<int, int>> swaps = cur.swaps;
swaps.push_back({i, j});
q.push(State{swaps, cur.moves + 1});
}
}
}
// cout << "Fastest fix is " << best.moves << " moves\n";
// for (auto &el : best.swaps) {
// cout << "Swapped " << el.first << " and " << el.second << "\n";
// }
return minimum;
}
