#include "shoes.h"
#include <bits/stdc++.h>
#define GOOD_LUCK ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define endl "\n"
#define ff first
#define ss second
#define pb push_back
#define all(v) v.begin(), v.end()
#define ll long long
using namespace std;
struct BIT{
int n;
vector <int> t;
void init(int n1) {
n = n1;
t.assign(n+2, 0);
}
int get(int r) {
int res=0;
while (r > 0) {
res += t[r];
r -= (r & (-r));
}
return res;
}
void upd(int i, int x) {
++i;
while (i <= n) {
t[i] += x;
i += (i & (-i));
}
}
int get(int l, int r) {
if (l > r) return 0;
++l, ++r;
if (l == 1) return get(r);
return get(r) - get(l-1);
}
};
ll get(vector <int> &a, vector <int> &b) { // a -> b
int n = a.size();
int mn = *min_element(all(a));
for (int i = 0; i < n; i++) {
a[i] -= mn;
b[i] -= mn;
}
// for (int &i : a) cerr << i << ' '; cerr << endl;
// for (int &i : b) cerr << i << ' '; cerr << endl;
int mx = *max_element(all(a));
BIT t;
t.init(n);
vector <int> pos[mx + 1];
for (int i = 0; i < n; i++) {
pos[a[i]].pb(i);
}
for (int i = 0; i <= mx; i++) reverse(all(pos[i]));
ll res = 0;
for (int i = 0; i < n; i++) {
int id = pos[b[i]].back();
pos[b[i]].pop_back();
res += 1LL * t.get(id+1, n-1);
t.upd(id, 1);
}
return res;
}
long long count_swaps(vector<int> v) {
int n = v.size();
vector <int> s;
vector <int> l[n+1], r[n+1];
for (int i = 0; i < n; i++) {
if (v[i] < 0) l[-v[i]].pb(i);
else r[v[i]].pb(i);
}
vector <int> pos(n, -1);
for (int i = 1; i <= n; i++) {
for (int j = 0; j < l[i].size(); j++) {
pos[l[i][j]] = r[i][j];
pos[r[i][j]] = l[i][j];
}
}
vector <int> is(n, 0);
for (int i = 0; i < n; i++) {
if (!is[i]) {
int x = i, y = pos[i];
if (v[x] > 0) swap(x, y);
s.pb(v[x]);
s.pb(v[y]);
is[x] = is[y] = 1;
}
}
return get(v, s);
}
