#include <iostream>
#include <vector>
#include <shoes.h>
#include <map>
#include <unordered_map>
#define int long long
#define mid(l, u) ((l+u)/2)
#define lchild(i) (i*2 + 1)
#define rchild(i) (i*2 + 2)
using namespace std;
int query(int l, int u, int i, int ll, int uu, int segtree[], int lazy[]){
if(lazy[i]){
segtree[i]+=(u-l+1)*lazy[i];
if(l!=u){
lazy[lchild(i)]+=lazy[i];
lazy[rchild(i)]+=lazy[i];
}
lazy[i] = 0;
}
if(l>=ll && u<=uu) return segtree[i];
if(l>uu || u<ll) return 0;
return query(l, mid(l, u), lchild(i), ll, uu, segtree, lazy) + query(mid(l, u)+1, u, rchild(i), ll, uu, segtree, lazy);
}
int update(int l, int u, int i, int ll, int uu, int segtree[], int lazy[]){
if(ll>uu) return 0;
if(lazy[i]){
segtree[i]+=(u-l+1)*lazy[i];
if(l!=u){
lazy[lchild(i)]+=lazy[i];
lazy[rchild(i)]+=lazy[i];
}
lazy[i] = 0;
}
if(l>=ll && u<=uu){
segtree[i] += (u-l+1);
if(l!=u){
lazy[lchild(i)]++;
lazy[rchild(i)]++;
}
return segtree[i];
}
if(l>uu || u<ll) return segtree[i];
return segtree[i] = update(l, mid(l, u), lchild(i), ll, uu, segtree, lazy) + update(mid(l, u)+1, u, rchild(i), ll, uu, segtree, lazy);
}
int count_swaps(vector<int32_t> s){
int n = s.size();
//cout<<n<<endl;
int segtree[4*n], lazy[4*n];
for(int i = 0;i<4*n;i++) segtree[i] = lazy[i] = 0;
unordered_map<int, vector<int>> mp;
for(int i = n-1;i>=0;i--){
mp[s[i]].push_back(i);
}
int ans = 0;
for(int i = 0;i<n;i++){
//cout<<i<<" "<<mp[-s[i]][mp[-s[i]].size()-1]<<endl;
if(mp[-s[i]][mp[-s[i]].size()-1]>i) continue;
int oind = mp[-s[i]][mp[-s[i]].size()-1];
int toadd;
if(s[i]>0){
toadd = i - oind - 1;
toadd-=query(0, n-1, 0, oind, oind, segtree, lazy);
}
else{
toadd = i - oind;
toadd-=query(0, n-1, 0, oind, oind, segtree, lazy);
}
//cout<<i<<" "<<mp[-s[i]]<<" "<<toadd<<endl;
ans+=toadd;
update(0, n-1, 0, oind+1, i-1, segtree,lazy);
mp[-s[i]].pop_back();
mp[s[i]].pop_back();
}
return ans;
}
