#include <bits/stdc++.h>
#include "shoes.h"
using namespace std;
const int mxN = 2e5 + 100;
int seg[mxN * 4], lazy[mxN * 4];
void build(int node, int start, int end){
if(start == end){
seg[node] = start;
return;
}
int mid = start + (end - start) / 2;
build(node * 2 + 1, start, mid);
build(node * 2 + 2, mid + 1, end);
}
void push(int node, int start, int end){
if(start == end){
seg[node] += lazy[node];
lazy[node] = 0;
return;
}
seg[node] += lazy[node];
lazy[node * 2 + 1] += lazy[node];
lazy[node * 2 + 2] += lazy[node];
lazy[node] = 0;
}
int query(int node, int start, int end, int idx){
push(node, start, end);
if(start == end) return seg[node];
int mid = start + (end - start) / 2;
if(idx <= mid) return query(node * 2 + 1, start, mid, idx);
return query(node * 2 + 2, mid + 1, end, idx);
}
void upd(int node, int start, int end, int l, int r){
push(node, start, end);
if(l > r) return;
if(start > r || end < l) return;
if(start >= l && end <= r){
lazy[node] = 1;
push(node, start, end);
return;
}
int mid = start + (end - start) / 2;
upd(node * 2 + 1, start, mid, l, r);
upd(node * 2 + 2, mid + 1, end, l, r);
seg[node] = seg[node * 2 + 1] + seg[node * 2 + 2];
}
long long count_swaps(std::vector<int> s) {
int n = (int) s.size();
long long ans = 0;
set<int> pos, neg;
build(0, 0, n - 1);
for(int i = 0; i < n; ++i){
if(s[i] < 0) neg.insert(i);
else pos.insert(i);
}
for(int i = 0; i < n; ++i){
auto lbn = neg.lower_bound(i);
auto lbp = pos.lower_bound(i);
if(*lbn != i && *lbp != i) continue;
if(s[i] > 0){
int tp = *neg.begin();
int curr = query(0, 0, n - 1, tp) - query(0, 0, n - 1, i);
ans += curr;
//cout << query(0, 0, n - 1, i) << " " << curr << endl;
upd(0, 0, n - 1, i, tp - 1);
neg.erase(tp);
pos.erase(pos.begin());
}else{
int tp = *pos.begin();
int curr = query(0, 0, n - 1, tp) - query(0, 0, n - 1, i) - 1;
ans += curr;
//cout << i << " " << curr << endl;
upd(0, 0, n - 1, i + 1, tp - 1);
pos.erase(tp);
neg.erase(neg.begin());
}
}
return ans;
}
/*
int main(){
freopen("input.in", "r", stdin);
freopen("output.out", "w", stdout);
//cout << count_swaps({1, 1, 1, -1, -1, -1}) << endl;
cout << count_swaps({-2, 2, 2, -2, -2, 2});
return 0;
}*/
