#include <bits/stdc++.h>
#include "shoes.h"
using namespace std;
// inline void setup()
// {
// #ifndef ONLINE_JUDGE
// freopen("test.inp", "r", stdin);
// freopen("test.out", "w", stdout);
// #endif
// ios_base::sync_with_stdio(0);
// cin.tie(0);
// cout.tie(0);
// }
class FENWICK_TREE
{
private:
long long tree_size;
vector<long long> tree;
public:
FENWICK_TREE(long long new_size)
{
tree_size = new_size;
tree.resize(tree_size + 1, 0);
}
void Update(long long pos, long long val)
{
while (pos <= tree_size)
{
tree[pos] += val;
pos += pos & (~(pos - 1));
}
}
long long Get(long long pos)
{
long long res = 0;
while (0 < pos)
{
res += tree[pos];
pos -= pos & (~(pos - 1));
}
return res;
}
};
long long count_swaps(vector<int> S)
{
int a;
long long res = 0;
queue<long long> neg[S.size() / 2 + 1], pos[S.size() / 2 + 1];
FENWICK_TREE ft(S.size());
S.insert(S.begin(), 0);
for (long long i = 1; i < S.size(); ++i)
{
if (S[i] < 0)
{
neg[-S[i]].push(i);
}
else
{
pos[S[i]].push(i);
}
}
for (long long i = 1, j = 1; i < S.size(); ++i)
{
if (S[i] == 0)
{
continue;
}
if (S[i] < 0)
{
a = pos[-S[i]].front();
res += a - i - (ft.Get(a) - ft.Get(i - 1)) - 1;
}
else
{
a = neg[S[i]].front();
res += a - i - (ft.Get(a) - ft.Get(i - 1));
}
S[a] = 0;
ft.Update(a, 1);
pos[abs(S[i])].pop();
neg[abs(S[i])].pop();
}
return res;
}
// int main()
// {
// setup();
// long long n;
// vector<int> v;
// cin >> n;
// v.resize(n);
// for (long long i = 0; i < n; ++i)
// {
// cin >> v[i];
// }
// cout << count_swaps(v);
// return 0;
// }
