#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <map>
#define ll long long
using namespace std;
vector <ll> sum, a;
void build(int id, int l, int r){
if(l == r){
sum[id] = 1;
return;
}
int m = (l + r) / 2, x = id * 2 + 1, y = x + 1;
build(x, l, m);
build(y, m + 1, r);
sum[id] = sum[x] + sum[y];
}
void update(int id, int l, int r, int i){
if(l == r){
sum[id] = 0;
return;
}
int m = (l + r) / 2, x = 2 * id + 1, y = x + 1;
if(i <= m){
update(x, l, m, i);
}
else{
update(y, m + 1, r, i);
}
sum[id] = sum[x] + sum[y];
}
ll query(int id, int l, int r, int L, int R){
if(L == l && r == R){
return sum[id];
}
int m = (l + r) / 2, x = id * 2 + 1, y = x + 1;
if(R <= m) return query(x, l, m, L, R);
if(L >= m + 1) return query(y, m + 1, r, L, R);
return query(x, l, m, L, m) + query(y, m + 1, r, m + 1, R);
}
long long count_swaps(vector<int> s) {
int n = s.size();
a.resize(n);
sum.resize(4 * n, 0);
for (int i = 0;i < n;i++) a[i] = s[i];
vector <vector <int>> adj(n / 2 + 1), adj1(n / 2 + 1); //adj = eyreg, adj1 = surug;
for (int i = 0;i < n;i++) {
if (s[i] < 0) {
adj1[-s[i]].push_back(i);
}
else {
adj[s[i]].push_back(i);
}
}
int id[n / 2 + 1] = {0};
// for (int i = 0;i < n;i++) {
// if (s[i] < 0) {
// adj1[-s[i]].push_back(i);
// }
// else {
// adj[s[i]].push_back(i);
// }
// }
// for (int i = 0;i < adj.size();i++) {
// cout << i << ": ";
// for (auto x : adj[i]) {
// cout << x << " ";
// }
// cout << endl;
// }
// for (int i = 0;i < adj1.size();i++) {
// cout << -i << ": ";
// for (auto x : adj1[i]) {
// cout << x << " ";
// }
// cout << endl;
// }
bool vis[n] = {0};
build(0, 0, n - 1);
ll res = 0;
for (int i = 0;i < n;i++) {
if (!vis[i]) {
if (s[i] < 0) {
if (adj1[-s[i]][id[-s[i]]] + 1 == adj[-s[i]][id[-s[i]]]) {
vis[i] = true;
vis[i + 1] = true;
id[-s[i]]++;
continue;
}
res += query(0, 0, n - 1, adj1[-s[i]][id[-s[i]]] + 1, adj[-s[i]][id[-s[i]]] - 1);
update(0, 0, n - 1, adj1[-s[i]][id[-s[i]]]);
update(0, 0, n - 1, adj[-s[i]][id[-s[i]]]);
vis[adj1[-s[i]][id[-s[i]]]] = true;
vis[adj[-s[i]][id[-s[i]]]] = true;
id[-s[i]]++;
}
else {
if (adj1[s[i]][id[s[i]]] - 1 == adj[s[i]][id[s[i]]]) {
vis[i] = true;
vis[i + 1] = true;
id[s[i]]++;
res++;
continue;
}
res += query(0, 0, n - 1, adj[s[i]][id[s[i]]] + 1, adj1[s[i]][id[s[i]]] - 1) + 1;
update(0, 0, n - 1, adj1[s[i]][id[s[i]]]);
update(0, 0, n - 1, adj[s[i]][id[s[i]]]);
vis[adj1[s[i]][id[s[i]]]] = true;
vis[adj[s[i]][id[s[i]]]] = true;
id[s[i]]++;
}
}
}
return res;
}
// int main() {
// cout << count_swaps({-2, 2, 2, -2, -2, 2});
// }
