#include "shoes.h"
#include <map>
#include <set>
#include <algorithm>
#include <tuple>
#include <iostream>
#include <queue>
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 7;
int bit[maxn];
void upd(int x) {
x++;
while (x < maxn) {
bit[x]++; x += x & (-x);
}
}
int qry(int x) {
int ans = 0; x++;
while (x > 0) {
ans += bit[x]; x -= x & (-x);
}
return ans;
}
vector < int > res;
map < int, queue < int > > M;
map < int, int > G;
long long count_swaps(std::vector<int> s) {
int n = s.size(); M.clear(); G.clear();
res.clear(); res.resize(n);
int cur = 0;
fill(bit, bit + n + n, 0);
for (int j = 0; j < n; j++) {
if (M.find(-s[j]) != M.end() && !M[-s[j]].empty()) {
int z = M[-s[j]].front(); M[-s[j]].pop();
int p = G[z];
if (s[j] < 0) {
res[p + p] = j; res[p + p + 1] = z;
} else {
res[p + p + 1] = j; res[p + p] = z;
}
} else {
if (M.find(s[j]) == M.end()) M[s[j]] = *new queue < int >();
M[s[j]].push(j);
G[j] = cur++;
}
}
ll ans = 0;
//for (int x : res) {
//cout << x << " ";
//}
//cout << endl;
for (int j = n - 1; j >= 0; j--) {
ans += qry(res[j]); upd(res[j]);
}
return ans;
}
