#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
/*
4
1 2 3 -4 4 -2 -1 -3
4
1 2 3 -4 -2 4 -1 -3
5
3 2 2 -2 3 2 -3 -2 -2 -3
4
1 2 3 4 -4 -3 -2 -1
5
1 2 3 4 4 -1 -2 -3 -4 -4
*/
int n;
map<vector<int>, int> used;
int mn = 30;
bool ok(vector<int> a) {
for(int i = 0; i < n; i+=2) {
if (a[i] == -a[i+1] && a[i] < 0) continue;
return false;
}
return true;
}
void go(vector<int> a, int swaps, vector<vector<int>> path, map<int, int> add) {
if (used.count(a) && used[a] <= swaps) return;
if (swaps >= mn) return;
used[a] = swaps;
if (ok(a)) {
// cout << swaps << "\n";
if (swaps < mn) {
mn = swaps;
cerr << mn << "\n";
for(auto i : path) {
for(int j : i) {
cout << j << " ";
}
cout << "\n";
}
cerr << "\n";
}
for(auto i : add) {
cout << i.first << " " << i.second << "\n";
}
return;
}
for(int i = 0; i < n; i++) {
vector<int> b = a;
if (i != 0) {
add[b[i]]++;
add[b[i-1]]++;
swap(b[i-1], b[i]);
path.push_back(b);
go(b, swaps+1, path, add);
path.pop_back();
add[b[i]]--;
add[b[i-1]]--;
swap(b[i-1], b[i]);
}
if (i != n-1) {
add[b[i]]++;
add[b[i+1]]++;
swap(b[i], b[i+1]);
path.push_back(b);
go(b, swaps+1, path, add);
add[b[i]]--;
add[b[i+1]]--;
path.pop_back();
swap(b[i], b[i+1]);
}
}
}
long long count_swaps(std::vector<int> s) {
n = s.size();
vector<int> a = s;
int sum = 0;
for(int i = 0; i < n; i += 2) {
for(int j = i+1; j < n; j++) {
if (a[i] == -a[j]) {
for(int k = j; k > i+1; k--) {
swap(a[k], a[k-1]);
sum++;
}
break;
}
}
if (a[i] > a[i+1]) {
swap(a[i], a[i+1]);
sum++;
}
// for(int j : a) {
// cout << j << " ";
// }
// cout << "\n";
}
// go(a, 0, temp1, temp2);
// cout << mn << "\n";
return sum;
}
