#include "shoes.h"
#include <bits/stdc++.h>
using namespace std ;
const int MAX = 1e5 + 10 ;
int tree[4 * MAX] ;
void update(int node , int l , int r , int idx)
{
if(idx > r || idx < l)
return ;
if(l == r)
{
tree[node] = 1;
return ;
}
int mid = (l + r) >> 1 ;
update(node << 1 , l, mid, idx) ;
update(node << 1 | 1 , mid + 1 ,r , idx) ;
tree[node] = tree[node << 1] + tree[node << 1 | 1] ;
}
int query(int node , int l , int r , int from , int to)
{
if(from > r || to < l)
return 0;
if(l >= from && r <= to)
return tree[node] ;
int mid = (l + r) >> 1 ;
int a = query(node << 1 , l , mid , from , to) ;
int b = query(node << 1 | 1 , mid + 1 , r , from , to) ;
return (a + b) ;
}
long long count_swaps(vector<int> v)
{
int ans = 0 ;
map<int, int>mp ;
int n = v.size() ;
int nxt[n], done[n];
memset(done, 0, sizeof(done)) ;
for(int i = n-1 ; i >= 0 ; --i)
{
mp[v[i]] = i ;
if(mp[-v[i]] == 0)
continue ;
nxt[i] = mp[-v[i]] ;
}
for(int i = 0 ; i < v.size() ; ++i)
{
if(done[i])
continue ;
done[nxt[i]] = 1 ;
ans += (nxt[i] - i - 1) ;
if(v[i] > 0)
ans++ ;
ans -= query(1 , 1 , n , i+1, nxt[i]) ;
update(1 , 1 , n , nxt[i] + 1) ;
}
return ans ;
}
