#include "shoes.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define f first
#define s second
struct SGT {
vector<int> data;
int size = 1;
SGT(int n) {
while(size < n) size *= 2;
data.resize(size * 2);
}
void set(int x, int val) {
x += size; data[x] = val; x /= 2;
for(int i = x; i > 0; i /= 2)
data[x] = data[2 * x] + data[2 * x + 1];
}
int sum(int l, int r) {
int s = 0;
for(l += size, r += size; l <= r; l /= 2, r /= 2) {
if(l % 2 == 1) s += data[l++];
if(r % 2 == 0) s += data[r--];
}
return s;
}
};
ll count_swaps(vector<int> a) {
ll ans = 0; int n = a.size();
SGT sgt = SGT(n);
set<pair<int, int>> prefix;
for(int i = 0; i < n; ++i) {
auto p = prefix.lower_bound({-a[i], 0});
if(p == prefix.end() || (*p).f != -a[i]) {
prefix.insert({a[i], i});
continue;
}
ans += i - (*p).s + sgt.sum((*p).s, i);
if(a[i] > 0) ans--;
sgt.set((*p).s, 1); sgt.set(i, -1);
prefix.erase(p);
}
return ans;
}
