#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()
using namespace std;
struct BIT{
int n;
vector <int> t;
void init(int n1) {
n = n1;
t.assign(n+1, 0);
}
int find(int l, int r) {
if (l > r) return 0;
if (l != 1) return find(1, r) - find(1, l-1);
int res=0;
while (r >= 1) {
res += t[r];
r -= (r & (-r));
}
return res;
}
void update(int i, int x) {
while (i <= n) {
t[i] += x;
i += (i & (-i));
}
}
int get(int l) {
l++;
return find(1, l);
}
void upd(int l, int r, int x) {
if (l > r) return;
l++, r++;
update(l, x);
if (r < n) update(r+1, -x);
}
};
long long get(vector <int> &v, vector <int> &s) {
int n = v.size();
vector <pair<int, int>> a, b;
for (int i = 0; i < n; i++) {
a.pb({v[i], i});
b.pb({s[i], i});
}
sort(all(a));
sort(all(b));
vector <int> pos(n);
for (int i = 0; i < n; i++) pos[b[i].ss] = a[i].ss;
// for (int &i : pos) cout << i << ' '; cout << endl;
long long res=0;
BIT t;
t.init(n);
for (int i = 1; i <= n; i++) t.upd(i, i, i);
for (int i = 0; i < n; i++) {
int id = t.get(pos[i]);
// cout << t.get(pos[i]) << ' ';
// cout << max(0, id - i) << ' ';
if (i > id) continue;
res += id - i;
t.upd(i, id, 1);
}
// cout << endl;
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);
}
