#include <bits/stdc++.h>
#include "shoes.h"
using namespace std;
const int MAXN = 200010;
int bit[MAXN];
void upd(int pos, int val) {
while(pos < MAXN) {
bit[pos] += val;
pos += pos & -pos;
}
}
int get(int pos) {
int ret = 0;
while(pos) {
ret += bit[pos];
pos -= pos & -pos;
}
return ret;
}
bool marked[MAXN];
int arr[MAXN];
vector<int> occurences[2 * MAXN];
long long count_swaps(std::vector<int> s) {
int n = (int)s.size() / 2;
int N = 2 * n;
long long ans = 0;
int pos = 1;
for(int i = 1; i <= N; i++) {
arr[i] = s[i - 1];
}
for(int i = N; i >= 1; i--) {
//printf("hey\n");
occurences[arr[i] + MAXN].push_back(i);
}
for(int _ = 0; _ < n; _++) {
while(marked[pos]) {
//printf("%d\n", pos);
pos += 1;
}
int num = arr[pos];
int target = -num;
int where = occurences[target + MAXN].back();
// printf("%d %d %d %d\n", pos, num, target, where);
marked[pos] = true;
marked[where] = true;
occurences[target + MAXN].pop_back();
occurences[num + MAXN].pop_back();
int cur_pos = where + (get(MAXN - 1) - get(where));
ans += cur_pos - (2 * _ + 2);
if(num > 0) ans += 1;
//printf("ans = %lld\n", ans);
upd(where, 1);
}
return ans;
}
