#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
long long count_swaps(std::vector<int> s) {
struct node{
int s,e,m;
int v;
node *l, *r;
node(int S, int E){
s = S;
e = E;
m = (s + e)/2;
v = 0;
if(s != e){
l = new node(s,m);
r = new node(m + 1, e);
}
}
int query(int S){
if(S <= s) return v;
if(S <= m) return r -> v + l -> query(S);
else return r -> query(S);
}
void update(int i){
v++;
if(s != e){
if(i <= m) l -> update(i);
else r -> update(i);
}
}
}*root;
int N = s.size();
map<int,int> cont;
map<int,int> freq;
map<pair<int,int>,int> mep;
int it = 0;
for(int i = 0; i < N; i++){
freq[s[i]]++;
if(freq[s[i]] > cont[abs(s[i])]){
mep[{abs(s[i]),freq[s[i]]}] = it;
it++;
cont[abs(s[i])]++;
}
}
vector<int> v;
freq.clear();
root = new node(0,N-1);
for(int i = 0; i < N; i++){
freq[s[i]]++;
if(s[i] > 0) v.push_back(mep[{s[i],freq[s[i]]}] * 2 + 1);
else v.push_back(mep[{abs(s[i]), freq[s[i]] }] * 2);
}
long long int ans = 0;
for(int i = 0; i < N; i++){
ans += root -> query(v[i]);
root -> update(v[i]);
}
return ans;
}
