#include "shoes.h"
#ifndef EVAL
#include "grader.cpp"
#endif
#include <bits/stdc++.h>
using namespace std;
struct segtree
{
int N;
vector<int> tree;
int upd(int index, int b, int e, int l, int r)
{
if (l <= b && e <= r)
return ++tree[index];
if (r <= b || e <= l)
return tree[index];
return upd(index * 2, b, (e + b) / 2, l, r) +
upd(index * 2 + 1, (e + b) / 2, e, l, r);
}
void upd(int l, int r)
{
upd(1, 0, N, l, r);
}
int query(int index, int b, int e, int pos, int cary)
{
tree[index] += cary;
if (pos < b || e <= pos)
return 0;
if (e - b == 1)
return tree[index];
int r = query(index * 2, b, (e + b) / 2, pos, tree[index]) +
query(index * 2 + 1, (e + b) / 2, e, pos, tree[index]);
tree[index] = 0;
return r;
}
int query(int pos)
{
int r = query(1, 0, N, pos, 0);
return r;
}
} tree;
long long count_swaps(std::vector<int> s)
{
tree.N = s.size();
tree.tree.resize(tree.N * 4 + 5, 0);
vector<int> posadd(s.size());
vector<bool> sorted(s.size(), false);
vector<queue<int>> pleft(s.size() + 1), pright(s.size() + 1);
iota(posadd.begin(), posadd.end(), 0);
long long numswaps = 0;
for (int i = 0; i < s.size(); i++)
(s[i] > 0 ? pright : pleft)[abs(s[i])].push(i);
for (int i = 1; i < s.size(); i++)
tree.upd(i, s.size());
for (int e, i = 0; i < s.size(); i++)
{
if (sorted[i])
continue;
(s[i] > 0 ? pright : pleft)[abs(s[i])].pop();
e = (s[i] < 0 ? pright : pleft)[abs(s[i])].front();
(s[i] < 0 ? pright : pleft)[abs(s[i])].pop();
sorted[i] = sorted[e] = true;
tree.upd(i + 1, e);
numswaps += tree.query(e) - tree.query(i) - 1;
if (s[i] > 0)
numswaps++;
}
return numswaps;
}
