#include "shoes.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <cstring>
#include <unordered_map>
using namespace std;
using ll = long long;
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define FORA(i, a) for (auto &i : a)
#define FORB(i, a, b) for (int i = a; i >= b; --i)
ll count_swaps(vector<int> s) {
int n = (int) s.size();
unordered_map<int, vector<int>> pos;
FORB(i, n - 1, 0) pos[s[i]].push_back(i);
vector<int> bit(n + 1, 0);
ll ans = 0;
FOR(i, 0, n - 1) if (pos[s[i]].back() == i) {
pos[s[i]].pop_back();
if (s[i] < 0) {
int j = pos[-s[i]].back();
pos[-s[i]].pop_back();
ans += i;
for (int x = i + 1; x > 0; x -= x & (-x)) ans -= bit[x];
for (int x = i + 1; x <= n; x += x & (-x)) ++bit[x];
ans += j;
for (int x = j + 1; x > 0; x -= x & (-x)) ans -= bit[x];
for (int x = j + 1; x <= n; x += x & (-x)) ++bit[x];
} else {
int j = pos[-s[i]].back();
pos[-s[i]].pop_back();
ans += j;
for (int x = j + 1; x > 0; x -= x & (-x)) ans -= bit[x];
for (int x = j + 1; x <= n; x += x & (-x)) ++bit[x];
ans += i;
for (int x = i + 1; x > 0; x -= x & (-x)) ans -= bit[x];
for (int x = i + 1; x <= n; x += x & (-x)) ++bit[x];
}
}
return ans;
}
