#include <bits/stdc++.h>
using namespace std;
struct Seg {
vector<int> arr{};
vector<int> a{};
int m;
Seg(vector<int> a) :a{a} {
const int n=a.size();
m=1;
do
{
m*=2;
} while (m<n);
arr.resize(2*m);
build(1, 0, m-1);
}
void build (int index, int l, int r) {
if (l==r) {
arr[index]=(index-m<a.size())?a[index-m]: 0;
return;
}
const int mid=(l+r)/2;
build(2*index, l, mid);
build(2*index+1, mid+1, r);
arr[index]=arr[2*index]+arr[2*index+1];
}
int query_helper(int index, int l, int r, int cover_l, int cover_r) {
if (r<cover_l) return 0;
if (l>cover_r) return 0;
if (l<=cover_l&&r>=cover_r) return arr[index];
const int mid=(cover_l+cover_r)/2;
return query_helper(2*index, l,r, cover_l, mid)+
query_helper(2*index+1, l,r,mid+1, cover_r);
}
int query (int l, int r) {
return query_helper(1, l, r, 0, m-1);
}
void update_helper(int index, int i, int x, int cover_l, int cover_r) {
if (cover_l==cover_r) {
arr[index]+=x;
return;
}
auto mid=(cover_l+cover_r)/2;
if (i<=mid) {
update_helper(2*index, i, x, cover_l, mid);
}
else {
update_helper(2*index+1, i, x, mid+1, cover_r);
}
arr[index]=arr[2*index]+arr[2*index+1];
}
void update(int i, int x) {
update_helper(1, i, x, 0, m-1);
}
};
int64_t count_swaps(vector<int> arr) {
const int n=arr.size();
vector<int> for_seg(n, 1);
Seg seg{for_seg};
unordered_map<int, deque<int>> indices{};
int64_t ans{};
for (auto i=0;i<arr.size();i++) {
auto num=arr[i];
auto opp=-num;
if (indices[opp].empty()) {
indices[num].push_front(i);
continue;
};
auto j=indices[opp].back();
indices[opp].pop_back();
auto between=(i==j+1)?0:seg.query(j+1,i-1);
ans+=between;
if (num<0) ans++;
seg.update(i, -1);
seg.update(j, 1);
}
return ans;
}
