#include <bits/stdc++.h>
using namespace std;
const int INF = 1000000;
struct binary_indexed_tree{
int N;
vector<int> BIT;
binary_indexed_tree(int N): N(N), BIT(N + 1, 0){
}
void add(int i, int x){
i++;
while (i <= N){
BIT[i] += x;
i += i & -i;
}
}
int sum(int i){
int ans = 0;
while (i > 0){
ans += BIT[i];
i -= i & -i;
}
return ans;
}
int sum(int L, int R){
return sum(R) - sum(L);
}
};
bool compare(vector<int> &a, vector<int> &b, int x, int y){
if (a[x] < a[y] && a[y] < b[x] && b[x] < b[y]){
return true;
}
if (a[y] < a[x] && a[x] < b[y] && b[y] < b[x]){
return false;
}
if (b[x] < a[y]){
return true;
}
if (b[y] < a[x]){
return false;
}
return x < y;
}
void merge_sort(vector<int> &A, vector<int> &a, vector<int> &b, int l, int r){
if (r - l == 1){
return;
}
int m = (l + r) / 2;
merge_sort(A, a, b, l, m);
merge_sort(A, a, b, m, r);
vector<int> ans;
int p1 = l, p2 = m;
while (!(p1 == m && p2 == r)){
if (p1 == m){
ans.push_back(A[p2]);
p2++;
} else if (p2 == r){
ans.push_back(A[p1]);
p1++;
} else if (compare(a, b, A[p1], A[p2])){
ans.push_back(A[p1]);
p1++;
} else {
ans.push_back(A[p2]);
p2++;
}
}
for (int i = 0; i < r - l; i++){
A[l + i] = ans[i];
}
}
long long count_swaps(vector<int> S){
int n = S.size() / 2;
vector<int> a, b, x;
vector<vector<int>> id1(n * 2 + 1);
vector<int> id2(n * 2 + 1);
for (int i = 0; i < n * 2; i++){
if (id1[-S[i] + n].size() == id2[-S[i] + n]){
id1[S[i] + n].push_back(i);
} else {
a.push_back(id1[-S[i] + n][id2[-S[i] + n]]);
b.push_back(i);
x.push_back(abs(S[i]));
id2[-S[i] + n]++;
}
}
vector<int> A(n);
for (int i = 0; i < n; i++){
A[i] = i;
}
merge_sort(A, a, b, 0, n);
vector<int> S2;
for (int i = 0; i < n; i++){
S2.push_back(-x[A[i]]);
S2.push_back(x[A[i]]);
}
map<int, deque<int>> Q2;
for (int i = 0; i < n * 2; i++){
Q2[S2[i]].push_back(i);
}
vector<int> p;
for (int i = 0; i < n * 2; i++){
p.push_back(Q2[S[i]].front());
Q2[S[i]].pop_front();
}
long long ans = 0;
binary_indexed_tree BIT(n * 2);
for (int i = 0; i < n * 2; i++){
ans += BIT.sum(p[i] + 1, n * 2);
BIT.add(p[i], 1);
}
return ans;
}
