#include "shoes.h"
#include <cstdio>
#include <cassert>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <numeric>
#include <cmath>
#include <iterator>
#include <set>
#include <map>
#include <math.h>
#include <iomanip>
#include <queue>
#include <unordered_set>
using namespace std;
using ll = long long;
struct segtree{
int size;
vector <int> values;
int NEUTRAL_ELEMENT = 0;
int merge(int a, int b){
return a + b;
}
void init(int n){
size = 1;
while (size < n) size *= 2;
values.resize(2 * size, 0);
}
void build(vector<int> &a, int x, int lx, int rx){
if (rx - lx == 1){
if (lx < a.size()){
values[x] = a[lx];
}
return;
}
int m = (lx + rx) / 2;
build(a, 2 * x + 1, lx, m);
build(a, 2 * x + 2, m, rx);
values[x] = merge(values[2 * x + 1], values[2 * x + 2]);
}
void build(vector<int> &a){
build(a, 0, 0, size);
}
void set(int i, int v, int x, int lx, int rx){
if (rx - lx == 1){
values[x] = v;
return;
}
int m = (lx + rx) / 2;
if (i < m){
set(i, v, 2 * x + 1, lx, m);
}
else{
set(i, v, 2 * x + 2, m, rx);
}
values[x] = merge(values[2 * x + 1], values[2 * x + 2]);
}
void set(int i, int v){
set(i, v, 0, 0, size);
}
int calc(int l, int r, int x, int lx, int rx){
if (lx >= r || l >= rx) return NEUTRAL_ELEMENT;
if (lx >= l && rx <= r) return values[x];
int m = (lx + rx) / 2;
int s1 = calc(l, r, 2 * x + 1, lx, m);
int s2 = calc(l, r, 2 * x + 2, m, rx);
return merge(s1, s2);
}
int calc(int l, int r){
return calc(l, r, 0, 0, size);
}
};
ll count_swaps(vector<int> a) {
ll n = a.size();
ll ans = 0;
segtree st;
st.init(n);
vector<int> used(n, 1);
st.build(used);
map<int,queue<int>> pos;
for (int i = 0; i < n; i++){
pos[a[i]].push(i + 1);
}
for (ll i = 0; i < n; i++){
if (used[i] == 0) continue;
int j = pos[-a[i]].front() - 1;
pos[-a[i]].pop();
pos[a[i]].pop();
st.set(i, 0);
st.set(j, 0);
used[i] = 0;
used[j] = 0;
int val = st.calc(i, j);
if (a[i] > 0) ans += val + 1;
else ans += val;
}
return ans;
}
