#ifndef NOTSUBMIT
#include <bits/stdc++.h>
#include "shoes.h"
using namespace std;
#endif
typedef long long ll;
typedef pair<int, int> pii;
#define fr first
#define sc second
set<int> cs; map<int, int> cc;
queue<pii> q[100020];
vector<pii> v;
const int N = 262144;
int tree[262150];
void upd(int pos, int val){ pos += 1;
for (int i = pos; i < N; i += i&-i){ tree[i] += val; }
}
int qry(int pos){ pos += 1;
int res = 0;
for (int i = pos; i > 0; i -= i&-i){ res += tree[i]; }
return res;
}
long long count_swaps(std::vector<int> s) {
int n = s.size();
for (int i = 0; i < n; i++){
if (s[i] > 0){ cs.insert(s[i]); }
}
int c = 0;
for (int x : cs){
c += 1;
cc[x] = c;
}
for (int i = 0; i < n; i++){
if (s[i] > 0){ s[i] = cc[ s[i] ]; }
else{ s[i] = -cc[ -s[i] ]; }
}
for (int i = 0; i < n; i++){
int idx = abs(s[i]);
//cout << "Q " << i << ' ' << s[i] << ' ';
if (q[idx].empty()){ q[idx].push({s[i], i}); /* cout << "PSH" << endl; */ }
else if (q[idx].front().fr == s[i]){ q[idx].push({s[i], i}); /* cout << "PSH" << endl; */ }
else{
v.push_back({ q[idx].front().sc, i }); /* cout << "PAIR " << q[idx].front().sc << ' ' << i << endl; */
q[idx].pop();
}
}
sort(v.begin(), v.end());
ll ans = 0;
for (int i = 0; i < n; i++){ upd(i, 1); }
for (pii p : v){
int i1 = p.fr, i2 = p.sc;
//cout << "P " << i1 << ' ' << i2 << endl;
ans += qry(i2) - qry(i1) - 1;
//cout << "QRY " << qry(i1) << ' ' << qry(i2) << endl;
if (s[i1] > s[i2]){ ans += 1; }
upd(i1, -1); upd(i2, -1);
}
return ans;
}
