#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> ii;
typedef vector<pair<int, int>> vii;
typedef vector<int> vi;
typedef long long ll;
#define PB push_back
#define MP make_pair
#define FOR(i, x, y) for (int i = x; i < y ; i ++)
const int MAXN = 2e5 + 5;
ll tree[MAXN];
void update(int a, int u){
a ++;
for(int k = a; k < MAXN; k += (k & -k)){
tree[k] += u;
}
}
ll sum(int a){
a ++;
ll res = 0;
for(int k = a; k >= 1; k -=(k &-k)){
res += tree[k];
}
//cout << a << " sum = " << res << '\n';
return res;
}
long long count_swaps(std::vector<int> s) {
memset(tree, 0, sizeof tree);
unordered_map<int, deque<int>> pos;
int sz = s.size();
for(int i = sz - 1; i >= 0; i--){
pos[s[i]].PB(i);
}
vector<bool> removed(sz, false);
ll swaps = 0;
vi d(2*sz, 0);//difference array for num of removed to right of it
for(int i = sz - 1; i >= 0; i --){
if (removed[i]) continue;
int pair = pos[-s[i]].front();
//cout << i << " pair index : " << pair << '\n';
pos[-s[i]].pop_front();
pos[s[i]].pop_front();
swaps += (i - pair - 1);
swaps -= sum(pair) - sum(i);
//update d in range 0 to pair
update(0, 1);
update(pair, -1);
if (s[i] < 0){
swaps ++;
}
removed[pair] = true;
//cout << swaps << '\n';
}
return swaps;
}
/*
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;
}
*/
