#include "shoes.h"
#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>
#define int long long
using namespace std;
struct segtree
{
vector<int> table;
void update(int k, int v, int l, int r, int pos)
{
if (l == r)
{
table[pos] = v;
return;
}
if (k <= (l + r) / 2) update(k, v, l, (l + r) / 2, 2*pos + 1);
else update(k, v, (l + r)/ 2 + 1, r, 2*pos + 2);
table[pos] = table[2*pos + 1] + table[2*pos + 2];
}
int query(int ql, int qr, int l, int r, int pos)
{
if (ql <= l && r <= qr) return table[pos];
if (ql > r || qr < l) return 0;
return query(ql, qr, l, (l + r)/2, 2*pos + 1) + query(ql, qr, (l + r)/2 + 1, r, 2*pos + 2);
}
};
long long count_swaps(vector<signed> s) {
int n = s.size();
vector<queue<int>> poss(n + 1);
vector<queue<int>> negs(n + 1);
for (int i = 0; i < n; i++)
{
if (s[i] < 0) negs[-s[i]].push(i);
else poss[s[i]].push(i);
}
vector<int> seq(n, -1);
int curr = 0;
for (int i = 0; i < n; i++)
{
if (seq[i] != -1) continue;
int v = abs(s[i]);
if (s[i] < 0)
{
seq[i] = curr;
seq[poss[v].front()] = curr + 1;
}
else
{
seq[negs[v].front()] = curr;
seq[i] = curr + 1;
}
poss[v].pop();
negs[v].pop();
curr += 2;
}
/*
for (auto i : seq) cout << i << " ";
cout << "\n";
*/
int ssum = 0;
segtree st;
st.table.resize(4*n, 0);
for (int i = 0; i < n; i++)
{
ssum += st.query(seq[i], n - 1, 0, n - 1, 0);
st.update(seq[i], 1, 0, n - 1, 0);
}
return ssum;
}
