#include <bits/stdc++.h>
using namespace std;
#define SZ(v) ((int)(v).size())
using ll = long long;
template<class T>
struct FenwickTree {
vector<T> bit;
int nb_elem;
FenwickTree(int N) {
nb_elem = N;
bit.resize(nb_elem);
for (int i(0); i < nb_elem; ++i)
bit[i] = 0;
}
FenwickTree(vector<T> a) : FenwickTree(SZ(a)) {
for (size_t i = 0; i < a.size(); i++)
add(i, a[i]);
}
T sum(int r) {
T ret = 0;
for (; r >= 0; r = (r & (r + 1)) - 1)
ret += bit[r];
return ret;
}
T sum(int l, int r) {
return sum(r) - sum(l - 1);
}
void add(int idx, T delta) {
for (; idx < nb_elem; idx = idx | (idx + 1))
bit[idx] += delta;
}
};
ll count_swaps(vector<int> shoes)
{
int nb_chaussures = SZ(shoes);
FenwickTree<ll> fen = FenwickTree<ll>(nb_chaussures);
ll nb_swaps(0);
map<int, queue<int>> pos;
pos[shoes[0]].push(0);
for (int i(1); i < nb_chaussures; ++i)
{
if (pos.find(-shoes[i]) != pos.end() and SZ(pos[-shoes[i]]))
{
int where = pos[-shoes[i]].front(); pos[-shoes[i]].pop();
nb_swaps += (i - where -1 + (shoes[i] < 0));
nb_swaps -= fen.sum(where, i);
fen.add(i, 1);
fen.add(where, -1);
}
else
pos[shoes[i]].push(i);
}
return nb_swaps;
}
