#include <bits/stdc++.h>
#include "shoes.h"
#define ll long long
#define ull unsigned long long
#define pb push_back
#define fi first
#define se second
#define ld long double
#define n_4 10010
#define n_5 100010
#define n_6 1000010
#define n_7 10000010
#define n_8 100000010
#define pii pair<int,int>
#define pll pair<long long,long long>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<ld, null_type,less<ld>, rb_tree_tag,tree_order_statistics_node_update>
// order_of_key -> # less than k
// find_by_order -> k-th element
// pq max element
const int NMAX = 20010;
ll seg[2*NMAX];
ll lejzi[2*NMAX];
ll nalaz[NMAX];
ll mikimaus[NMAX];
void update(int l, int r, int nl, int nr, int node, int value) {
if ( l <= nl && r >= nr ) {
lejzi[node] += value;
return;
}
if ( r < nl || l > nr ) return;
update(l, r, (nl+nr)/2+1, nr, node*2+2, value);
update(l, r, nl, (nl+nr)/2, node*2+1, value);
}
ll pronadji(int ind, int nl, int nr, int node) {
if ( nl == nr ) {
seg[node] += lejzi[node];
lejzi[node] = 0;
return seg[node];
}
seg[node] += lejzi[node];
lejzi[node*2+1] += lejzi[node];
lejzi[node*2+2] += lejzi[node];
lejzi[node] = 0;
if ( ind <= (nl + nr)/2 ) {
return pronadji(ind, nl, (nl + nr)/2, node*2+1);
}
else {
return pronadji(ind, (nl + nr)/2+1, nr, node*2+2);
}
}
ll count_swaps(vector<int>v) {
ll N = v.size();
unordered_map<ll,ll>m;
for (int i = 0 ; i < N; i++ ) {
m[v[i]] = i;
if ( m.find(-v[i]) != m.end() ) {
nalaz[i] = m[-v[i]];
}
else nalaz[i] = -1;
}
for (int i = N-1; i >= 0 ; i-- ) {
if ( nalaz[i] != -1) {
mikimaus[nalaz[i]] = i;
}
}
ll rez = 0;
for (int i = 0 ; i < N; i++ ) {
if (mikimaus[i] ) {
ll r = mikimaus[i] + pronadji(mikimaus[i],0,N-1,0);
ll l = i + pronadji(i,0,N-1,0);
ll cnt = r-l-1;
if ( v[i] > 0 ) cnt++;
l = i + 1;
r = mikimaus[i]-1;
if ( r >= l ) {
update(l,r,0,N-1,0,1);
}
rez += cnt;
}
}
return rez;
}
