#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pll;
#define X first
#define Y second
#define sep ' '
const int MAXN = 2e6 + 10;
int n, fen[MAXN];
map<int, vector<int>> mp;
inline void update(int ind, int val) {
for (++ind; ind < MAXN; ind += ind & -ind)
fen[ind] += val;
}
inline int query(int ind) {
int ans = 0;
for (++ind; ind > 0; ind -= ind & -ind)
ans += fen[ind];
return ans;
}
inline int query(int l, int r) {
if (r < l) return 0;
int ans = query(r);
if (l) ans -= query(l - 1);
return ans;
}
ll count_swaps(vector<int> vec) {
ll ans = 0;
n = vec.size();
for (int i = n - 1; i >= 0; i--)
mp[vec[i]].push_back(i);
for (int i = 0; i < n; i++) {
if (query(i, i)) continue;
int ind = mp[-vec[i]].back();
mp[vec[i]].pop_back();
mp[-vec[i]].pop_back();
if (vec[i] > 0) ans++;
ans += ind - i - 1 - query(i + 1, ind - 1);
update(i, 1);
update(ind, 1);
}
return ans;
}
