#include "shoes.h"
/*
Telebe of Adicto && Mamedov yani AzeTurk810
I see humans but no humanity
*/
#include <algorithm>
#include <cassert>
#include <iostream>
#include <utility>
#include <vector>
// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
using ll = long long;
using namespace std;
#define ln '\n'
#define INFi 1e9
#define INFll 1e18
#ifdef ONPC
#include <algo.hpp>
#else
#define dbg(...)
#define dbg_out(...)
#endif
size_t _n;
ll ans;
vector<int> S;
vector<vector<int>> pos_l, pos_r;
template <typename T>
struct BIT {
size_t _n;
vector<T> tree;
BIT(int n) : _n(n + 1), tree(n + 2, 0) {}
void add(int i, int val) {
i++;
for (; i <= _n; i += i & -i) {
// dbg(i);
tree[i] += val;
}
}
T ask(int l, int r) {
l++, r++;
// dbg("bit");
// dbg(make_pair(l, r));
if (l != 1) {
return ask(0, r) - ask(0, l - 1);
}
T res = 0;
for (; r > 0; r -= r & -r) {
dbg(r);
res += tree[r];
}
return res;
}
};
inline void systemd() {
assert(S.size() == _n);
pos_l.clear();
pos_r.clear();
pos_l.resize(_n + 1);
pos_r.resize(_n + 1);
ans = 0;
}
char solve() {
systemd();
for (size_t i = 0; i < _n; i++) {
if (S[i] < 0) {
pos_l[-S[i]].push_back(i);
} else {
pos_r[S[i]].push_back(i);
}
}
for (size_t i = 0; i <= _n; i++) {
reverse(pos_r[i].begin(), pos_r[i].end());
}
vector<pair<int, int>> V;
for (size_t i = 0; i < _n; i++) {
if (S[i] > 0)
continue;
int id = pos_r[-S[i]].back();
if (i < id)
V.push_back({i, id});
else {
ans++;
V.push_back({id, i});
}
pos_r[-S[i]].pop_back();
}
BIT<ll> t(_n + 1);
for (auto [l, r] : V) {
ans += r - l - 1;
// dbg(make_pair(l, r));
ans -= t.ask(l, r);
// dbg(make_pair(l, r));
t.add(l, -1);
// dbg(make_pair(l, r));
t.add(r, 1);
dbg(make_pair(l, r));
dbg(ans);
}
return 1;
}
long long count_swaps(std::vector<int> s) {
_n = s.size();
S = s;
assert(solve());
return ans;
}
