#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
struct SegmentTree
{
int N;
vector<int> tree;
SegmentTree(int _N) : N(_N), tree(4*_N){
}
int query(int p, int q, int id, int L, int R)
{
if (L > q or R < p)
return 0;
if (p <= L and R <= q)
return tree[id];
int mid = (L + R) / 2;
return query(p, q, 2*id, L, mid) + query(p, q, 2*id+1, mid+1, R);
}
int query(int p, int q)
{
return query(p, q, 1, 0, N-1);
}
void increase(int p, int val, int id, int L, int R)
{
if (p < L or p > R)
return;
if (L == R) {
tree[id] += val;
return;
}
int mid = (L + R) / 2;
increase(p, val, 2*id, L, mid);
increase(p, val, 2*id+1, mid+1, R);
tree[id] = tree[2*id] + tree[2*id+1];
}
void increase(int p, int val)
{
increase(p, val, 1, 0, N-1);
}
};
long long count_swaps(std::vector<int> s)
{
vector< pair<int,int> > parejas;
map<int,queue<int> > last;
for (int i = int(s.size())-1; i >= 0; --i)
{
int x = s[i];
if (!last[-x].empty())
{
parejas.emplace_back(i, last[-x].front());
last[-x].pop();
}
else
last[x].push(i);
}
reverse(parejas.begin(), parejas.end());
long long ret = 0;
SegmentTree st(s.size());
for (auto p : parejas)
{
int l, r;
tie(l, r) = p;
int steps = r - l - 1 - st.query(l+1, r-1);
if (s[l] > 0) {
++steps;
}
ret += steps;
st.increase(r, 1);
}
return ret;
}
