#include "shoes.h"
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
using ll = long long;
/*
2
2 1 -1 -2
3
-2 2 2 -2 -2 2
4
4 4 4 4 -4 -4 -4 -4
*/
struct Fenwick {
int n;
vector<int> bit;
Fenwick(int n) {
this->n = n;
bit = vector<int>(n + 1);
}
void update(int i, int d) {
i++;
for (; i <= n; i += i & -i) {
bit[i] += d;
}
}
int sum(int i) {
int res = 0;
i++;
for (; i > 0; i -= i & -i) {
res += bit[i];
}
return res;
}
};
long long count_swaps(std::vector<int> s) {
ll res = 0;
int N = s.size();
Fenwick tree(N);
map<int, queue<int>> mp;
vector<bool> used(N);
for (int i = 0; i < N; ++i) {
mp[s[i]].push(i);
}
for (int i = 0; i < N; ++i) {
if (used[i]) continue;
mp[s[i]].pop();
int want = -s[i];
int id = i + tree.sum(i);
int nxt = mp[want].front();
mp[want].pop();
res += nxt - id - 1 + tree.sum(nxt);
// cout << nxt << " " << id << endl;
if (want < s[i]) {
res++;
}
tree.update(i, 1);
tree.update(nxt, -1);
used[nxt] = true;
// for (int j = 0; j < N; ++j) {
// cout << tree.sum(j) << " ";
// }
// cout << endl;
}
// for (int i = 0; i < N; i += 2) {
// int want = -s[i];
// for (int j = i + 1; j < N; ++j) {
// if (s[j] == want) {
// int k = j;
// // cerr << N << " = ";
// // cerr << i << " = " << want << endl;
// while (k - 1 != i) {
// swap(s[k - 1], s[k]);
// k--;
// res++;
// }
// if (s[k - 1] > s[k]) {
// swap(s[k - 1], s[k]);
// res++;
// }
// break;
// }
// }
// for (auto& u : s) {
// cout << u << " ";
// }
// cout << endl;
// }
// for (int i = 0; i < )
// for (auto& u : s) {
// cout << u << " ";
// }
// cout << endl;
return res;
}
// int main() {
// int n;
// assert(1 == scanf("%d", &n));
// vector<int> S(2 * n);
// for (int i = 0; i < 2 * n; i++)
// assert(1 == scanf("%d", &S[i]));
// fclose(stdin);
// long long result = count_swaps(S);
// printf("%lld\n", result);
// fclose(stdout);
// return 0;
// }
