#include "shoes.h"
#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define mp make_pair
#define all(x) x.begin(), x.end()
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef pair<LL, LL> pll;
vector<int> pl[100010], mi[100010];
vector<pair<pii, int> >arr;
struct SEGMENT_TREE {
struct NODE {
int st, fin;
LL q;
} tree[1000000];
int x;
const LL inf=987654321987654321;
LL f(LL a, LL b){return a+b;}
void maketree(int point, int num) {
if(num==1)tree[point].st=tree[point].fin=++x;
if(num<=1)return;
maketree(point*2, num-num/2);
maketree(point*2+1, num/2);
tree[point].st=tree[point*2].st;
tree[point].fin=tree[point*2+1].fin;
}
LL query(int a, int b, int point) {
if(tree[point].st>=a&&tree[point].fin<=b)
return tree[point].q;
if(tree[point].st>b||tree[point].fin<a)
return 0;
return f(query(a, b, point*2), query(a, b, point*2+1));
}
void updaterange(int point, int num, LL p) {
if(tree[point].st==tree[point].fin) {
tree[point].q=p;
return;
}
if(num<=tree[point*2].fin)updaterange(point*2, num, p);
else updaterange(point*2+1, num, p);
tree[point].q=f(tree[point*2].q, tree[point*2+1].q);
}
void init(int n) {
maketree(1, n);
}
LL get_query(int a, int b) {
return query(a, b, 1);
}
void update(int a, LL num) {
updaterange(1, a, num);
}
}seg;
LL count_swaps(std::vector<int> s) {
LL ans=0;
for(int i=0; i<s.size(); i++){
if(s[i]<0)mi[-s[i]].pb(i+1);
else pl[s[i]].pb(i+1);
}
for(int i=1; i<=100000; i++){
for(int j=0; j<pl[i].size(); j++){
if(mi[i][j]<pl[i][j])arr.pb(mp(mp(mi[i][j], pl[i][j]), 0));
else arr.pb(mp(mp(pl[i][j], mi[i][j]), 1));
}
}
sort(all(arr));
seg.init(s.size());
for(int i=1; i<=s.size(); i++)seg.update(i, 1);
for(int i=0; i<arr.size(); i++){
//printf("%d %d\n", arr[i].F.F, arr[i].F.S);
ans+=seg.get_query(arr[i].F.F+1, arr[i].F.S-1)+(LL)arr[i].S;
seg.update(arr[i].F.F, 0);
seg.update(arr[i].F.S, 0);
}
return ans;
}
