#include <bits/stdc++.h>
#include <cmath>
#include "shoes.h"
using namespace std;
#define ll long long
const ll mmod = 998244353;
#define vl vector<long long>
#define vll vector<vector<long long>>
#define pl pair<long long, long long>
#define vb vector<bool>
void build(ll l, ll r, ll i, vl& tree){
if (l == r){
tree[i] = 1;
return;
}
ll mid = (l+r)/2;
build(l, mid, 2*i, tree);
build(mid+1, r, 2*i+1, tree);
tree[i] = tree[2*i] + tree[2*i+1];
return;
}
void update(ll l, ll r, ll p, ll i, vl& tree){
if (l == p && r == p){
tree[i] = 0;
return;
}
if (p < l || r < p){
return;
}
ll mid = (l+r)/2;
update(l, mid, p, 2*i, tree);
update(mid+1, r, p, 2*i+1, tree);
tree[i] = tree[2*i] + tree[2*i+1];
return;
}
ll query(ll l, ll r, ll L, ll R, ll i, vl& tree){
if (L <= l && r <= R){
return tree[i];
}
if (r < L || R < l){
return 0;
}
ll mid = (l+r)/2;
ll a = query(l, mid, L, R, 2*i, tree);
ll b = query(mid+1, r, L, R, 2*i+1, tree);
return a + b;
}
ll count_swaps(vector<int> S){
ll n = S.size();
vl nums;
for (ll i = 0; i < n; i++){nums.push_back(S[i]);}
vll occ (n/2+1);
vl pairs (n);
for (ll i = 0; i < n; i++){
ll p = abs(nums[i]);
if (occ[p].empty()){
occ[p].push_back(i);
continue;
}
if (nums[occ[p][occ[p].size() -1]] == nums[i]){
occ[p].push_back(i);
}
else{
ll pos = occ[p][occ[p].size() - 1];
pairs[pos] = i;
pairs[i] = pos;
occ[p].pop_back();
}
}
vl tree (4*n + 4, 0);
ll s = 1;
while (s < n){
s *= 2;
}
s--;
build(0, s, 1, tree);
ll suma = 0;
for (ll i = 0; i < n; i++){
ll j = pairs[i];
if (j-1 > i){
suma += query(0, s, i+1, j-1, 1, tree);
update(0,s,j,1, tree);
}
if (j > i && nums[j] < 0){
suma++;
}
}
return suma;
}
