#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
#define sp << " " <<
class segtre{
private:
int sz;
vector<int> tre;
void _update(int x, int d, int l, int r, int s){
if (l > x || r < x)
return;
if (l == r){
tre[s] += d;
return;
}
int m = (l + r) >> 1;
_update(x, d, l, m, s << 1);
_update(x, d, m + 1, r, (s << 1) | 1);
tre[s] = tre[s << 1] + tre[(s << 1) | 1];
}
int _query(int tl, int tr, int l, int r, int s){
if (l > tr || r < tl)
return 0;
if (tl <= l && r <= tr){
return tre[s];
}
int m = (l + r) >> 1;
return _query(tl, tr, l, m, s << 1) + _query(tl, tr, m + 1, r, (s << 1) | 1);
}
public:
void init(int size){
sz = size;
tre.resize(size * 4);
}
void update(int konum, int add){
_update(konum, add, 0, sz - 1, 1);
}
int query(int l, int r){
return _query(l, r, 0, sz - 1, 1);
}
};
long long count_swaps(std::vector<int> s) {
segtre tre;
int n = s.size();
tre.init(n);
map<int, vector<int>> zip;
int j = 1;
for (int i = 0; i < n; i++){
if (s[i] < 0)
continue;
zip[-s[i]].push_back(-j);
s[i] = j;
j++;
}
for (int i = n - 1; i >= 0; i--){
if (s[i] > 0)
continue;
int tmp = s[i];
s[i] = zip[tmp].back();
zip[tmp].pop_back();
}
long long int ret = 0;
map<int, int> mp;
for (int i = 0; i < n; i++){
if (mp[abs(s[i])]){
ret += i - mp[abs(s[i])];
if (s[i] < 0)
ret += 1;
tre.update(i, -1);
mp[abs(s[i])] = i;
}else{
mp[abs(s[i])] = i + 1;
tre.update(i, 1);
}
}
for (int i = 0; i < n; i++){
if (s[i] == 0)
continue;
ret -= tre.query(i, mp[abs(s[i])]);
// tre.update(i, -1); // this doesn't needed
tre.update(mp[abs(s[i])], 1);
s[mp[abs(s[i])]] = 0;
}
return ret;
}
