#include "shoes.h"
#include <stdio.h>
#include <iostream>
#include <queue>
#include <unordered_set>
#include <math.h>
using namespace std;
bool is_valid(vector<int>& arr) {
for (int i = 0; i < arr.size()/2; i++) {
if (abs(arr[i*2]) != abs(arr[i*2+1])) return false;
if (arr[i*2] > 0 || arr[i*2+1] < 0) return false;
}
return true;
}
string arr_to_str(vector<int>& arr) {
string s = "";
for (int el : arr) {
s += to_string(el) + ",";
}
return s;
}
long long count_swaps(std::vector<int> s) {
// solve it meow
queue<pair<int,vector<int>>> next;
next.push(make_pair(0,s));
unordered_set<string> memo;
memo.insert(arr_to_str(s));
while (!next.empty()) {
// check if this array is valid
if (is_valid(next.front().second)) return next.front().first;
for (int i = 0; i < s.size()-1; i++) {
vector<int> arr = next.front().second;
swap(arr[i], arr[i+1]);
string key = arr_to_str(arr);
if (memo.count(key) == 0) {
next.push(make_pair(next.front().first+1, arr));
memo.insert(key);
}
}
next.pop();
}
return 0;
}
