#include "shoes.h"
#include <cassert>
#include <iostream>
#include <iterator>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <cstdio>
#define rep(i,a,b) for(int i = a; i<b; i++)
#define per(i,a,b) for(int i = a; i>=b; i--)
#define pb push_back
#define se second
using namespace std;
void update(vector <int>&tre, int v, int l, int r, int pos, int val){
if(l==r){
tre[v]=val;
return;
}
int m = (l+r)/2;
if(pos<=m){
update(tre, v+v, l, m, pos, val);
}else{
update(tre, v+v+1, m+1, r, pos, val);
}
tre[v] = tre[v+v] + tre[v+v+1];
}
int sum(vector <int>&tre, int v, int l, int r, int rl, int rr){
if(r<rl||rr<l){
return 0;
}
if(rl<=l&&r<=rr){
return tre[v];
}
int m = (l+r)/2;
return sum(tre, v+v, l, m, rl, rr)+sum(tre,v+v+1, m+1, r, rl , rr);
}
long long count_swaps(vector<int> s) {
int n = s.size();
long long ans = 0;
map <int, vector <int> > m;
vector <int> tree(4*(n+4), 0);
rep(i,0,n){
update(tree, 1,1,n+2,i+1, 1);
}
rep(i,0,n){
m[s[i]].pb(i);
}
for(auto& vec:m){
reverse(vec.se.begin(), vec.se.end());
}
vector <int> vis(n+n, 0);
rep(i,0,n){
if(vis[i])continue;
//cout << i << " ";
if(s[i]<0){
int pos = m[-s[i]].back();
//cout << pos << " 1" << endl;
ans += sum(tree, 1, 1, n+2, i+2, pos);
update(tree, 1,1,n+2,i+1, 0);
update(tree, 1,1,n+2,pos+1, 0);
vis[i]=1;
vis[pos]=1;
}else{
int pos = m[-s[i]].back();
//cout << pos << " 2" << endl;
ans += sum(tree, 1, 1, n+2, i+1, pos);
update(tree, 1,1,n+2,i+1, 0);
update(tree, 1,1,n+2,pos+1, 0);
vis[i]=1;
vis[pos]=1;
}
m[-s[i]].pop_back();
m[s[i]].pop_back();
//cout << ans << endl;
}
//cout << "ans: " << ans << endl;
return ans;
}
