// #include "shoes.h"
#include "bits/stdc++.h"
using namespace std;
vector<int> sum;
void init(int n)
{
int sz = 1;
while(sz <= n)
sz *= 2;
sum.assign(2 * sz , 0);
}
void update(int id , int val , int nd , int lnd , int rnd)
{
if(lnd == rnd)
{
sum[nd] = val;
return;
}
int mid = (lnd + rnd) / 2;
if(id <= mid)
update(id , val , 2 * nd , lnd , mid);
else
update(id , val , 2 * nd + 1 , mid + 1 , rnd);
sum[nd] = sum[2 * nd] + sum[2 * nd + 1];
}
int query(int l , int r , int nd , int lnd , int rnd)
{
if(l <= lnd && rnd <= r)
return sum[nd];
if(l > rnd || r < lnd)
return 0;
int mid = (lnd + rnd) / 2;
return query(l , r , 2 * nd , lnd , mid) + query(l , r , 2 * nd + 1 , mid + 1 , rnd);
}
long long count_swaps(std::vector<int> s) {
long long n = s.size();
init(n);
map<int , deque<int>> inx;
for(int i = 1 ; i <= n ; i++)
inx[s[i - 1]].push_back(i) , update(i , 1 , 1 , 1 , n);
int use[n + 5] = {};
long long ans = 0;
for(int i = 1 ; i <= n ; i++)
{
if(use[i] == 1)
continue;
int j = inx[-s[i - 1]].front();
inx[-s[i - 1]].pop_front();
inx[s[i - 1]].pop_front();
if(s[i - 1] > 0)
ans += query(i , j , 1 , 1 , n) - 1;
else
ans += query(i , j , 1 , 1 , n) - 2;
use[i] = 1 , use[j] = 1;
update(i , 0 , 1 , 1 , n);
update(j , 0 , 1 , 1 , n);
}
return ans;
}
