#include "shoes.h"
#include <vector>
#include <map>
#include <queue>
#include <algorithm>
#include <iostream>
#include <cassert>
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;
}
// cerr << l << ' ' << r << ' ' << steps << endl;
ret += steps;
st.increase(r, 1);
}
return ret;
/*
// subtask 5
long long ret = 0;
for (int i = 0; i < int(s.size()); i += 2) {
int j;
for (j = i+1; j < int(s.size()); j++) {
if (s[j] == -s[i])
break;
}
assert( j < int(s.size()) );
int steps = 0;
for (; j > i+1; --j) {
swap(s[j], s[j-1]);
++steps;
}
if (s[j] < 0) {
swap(s[j], s[i]);
++steps;
}
ret += steps;
}
return ret;
*/
}
