#include "shoes.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 4e5+5;
int st[N], n=0;
void add(int i, int x, int l=0, int r=n, int cur=1)
{
st[cur] += x;
if(l == r)
return;
int mid = (l+r)/2;
if(i <= mid)
add(i, x, l, mid, 2*cur);
else
add(i, x, mid+1, r, 2*cur+1);
}
int cnt(int lg, int rg, int l=0, int r=n, int cur=1)
{
if(rg < lg)
return 0;
if(rg < l || r < lg)
return 0;
if(lg <= l && r <= rg)
return st[cur];
int mid = (l+r)/2;
return cnt(lg, rg, l, mid, 2*cur) + cnt(lg, rg, mid+1, r, 2*cur+1);
}
vector<int> p[3*N];
ll count_swaps(vector<int> s)
{
n = s.size();
for(int i=n-1; i>=0; i--)
p[N+s[i]].push_back(i);
for(int i=0; i<n; i++)
add(i, 1);
ll ans = 0;
for(int i=0; i<n; i++)
{
if(cnt(i, i) == 0)
continue;
int pa = -s[i];
int id = p[N+pa].back();
p[N+pa].pop_back();
ans += cnt(i+1, id-1);
if(s[i] > 0)
ans++;
add(i, -1);
add(id, -1);
}
return ans;
}
