#include<bits/stdc++.h>
using namespace std;
int64_t count_swaps(vector<int> S){
struct node{
int s,e,m;
int64_t val;
node *l, *r;
node(int _s,int _e):
s(_s),e(_e),m((_s+_e)/2),val(0){
if (s!=e){
l = new node(s,m);
r = new node(m+1,e);
}
}
void update(int p, int v){
if (s==e) {val+=v;return;}
if (p>m) r->update(p,v);
else l->update(p,v);
val = l->val+r->val;
}
int64_t query(int a, int b){
if (b<s or a>e) return 0;
if (a<=s and b>=e) return val;
return l->query(a,b)+r->query(a,b);
}
};
node *root = new node(0,S.size()-1);
for (int i = 0;i<S.size();i++) root->update(i,1);
vector<vector<int64_t> >l;
vector<vector<int64_t> >r;
l.resize(S.size()/2+1);
r.resize(S.size()/2+1);
int64_t ans = 0;
for (int i = 0;i<S.size();i++){
if (S[i]<0) {
l[S[i]*-1].push_back(i);
}
else{
r[S[i]].push_back(i);
}
}
vector<int> c;
c.assign(S.size()/2+1,0);
vector<pair<int,int> > c1;
for (int i = 0;i<S.size();i++){
int a;
if (S[i]>0) {
a = c[S[i]];
if (l[S[i]][a]>r[S[i]][a]){
c1.push_back(make_pair(l[S[i]][a],r[S[i]][a]));
}
c[S[i]]++;
}
else {
a = c[S[i]*-1];
if (l[S[i]*-1][a]<r[S[i]*-1][a]){
c1.push_back(make_pair(l[S[i]*-1][a],r[S[i]*-1][a]));
}
c[S[i]*-1]++;
}
}
for (int i = 0;i<c1.size();i++){
if (c1[i].first>c1[i].second){
ans = ans+root->query(c1[i].second,c1[i].first-1);
root->update(c1[i].first,-1);
root->update(c1[i].second,1);
}
else{
ans = ans+root->query(c1[i].first+1,c1[i].second-1);
root->update(c1[i].first,1);
root->update(c1[i].second,-1);
}
}
return ans;
}
