#include "shoes.h"
using namespace std;
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i = a; i < b; i++)
typedef long long ll;
// SUM TREE
struct SegmTree {
vector<ll> T; int n;
SegmTree(int n) : T(2 * n, (ll)0), n(n) {}
void Update(int pos, ll val) {
for (T[pos += n] = val; pos > 1; pos /= 2)
T[pos / 2] = T[pos] + T[pos ^ 1];
}
ll Query(int b, int e) {
ll res = 0;
for (b += n, e += n; b < e; b /= 2, e /= 2) {
if (b % 2) res = res + T[b++];
if (e % 2) res = res + T[--e];
}
return res;
}
};
long long count_swaps(std::vector<int> arr) {
int n = arr.size();
ll ans = 0;
vector<queue<int>> pos(n);
vector<int> cnt(n, 0);
rep(i,0,n) {
if (arr[i] > 0) {
cnt[arr[i]]--;
if (cnt[arr[i]] < 0) pos[arr[i]].push(i);
}
else {
cnt[-arr[i]]++;
if (cnt[-arr[i]] <= 0) {
int j = pos[-arr[i]].front();
pos[-arr[i]].pop();
swap(arr[i], arr[j]);
ans++;
}
}
}
vector<vector<int>> p2index(n);
vector<int> pointer(n, 0);
rep(i,0,n) if (arr[i] > 0) p2index[arr[i]].push_back(i);
SegmTree tr(n);
rep(i,0,n) {
if (arr[i] > 0) continue;
ll here = i - tr.Query(0, i);
tr.Update(i, 1);
int nei = p2index[-arr[i]][pointer[-arr[i]]];
here += nei - tr.Query(0, nei);
tr.Update(nei, 1);
pointer[-arr[i]]++;
ans += here;
}
return ans;
}
/*
int main() {
int n;
cin >> n;
vector<int>arr(n);
rep(i,0,n) cin >> arr[i];
cout << count_swaps(arr) << endl;
}
*/
