#include "shoes.h"
#include <bits/stdc++.h>
#define FOR(i, begin, end) for(int i=(begin); i<(end); i++)
#define pb push_back
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
const int N=2e5+10;
int n, cn[N];
vi max_pos[N][2];
void add_cn(int p)
{
p++;
for(int i=p; i<N; i+=i&(-i)) cn[i]++;
}
int get_cn(int p)
{
p++;
int ret=0;
for(int i=p; i>0; i-=i&(-i)) ret+=cn[i];
return ret;
}
int range(int i, int j)
{
if(i>j) return 0;
return get_cn(j)-get_cn(i-1);
}
long long count_swaps(vector<int> s) {
n=s.size();
FOR(i, 0, n)
{
int x=abs(s[i]), y=s[i]<0?0:1;
max_pos[x][y].pb(i);
}
ll ans=0;
int neg=0;
vector<bool> used(n, false);
for(int i=n-1; i>=0; i--){
// cout << i << ": ";
// FOR(i, 0, n) cout << used[i];
// cout << endl;
while(i>=0 && used[i]){
i--;
neg--;
}
if(i<0) break;
max_pos[abs(s[i])][s[i]<0?0:1].pop_back();
if(s[i]<0){
assert(!max_pos[-s[i]][1].empty());
int true_i=i-neg, j=max_pos[-s[i]][1].back();
max_pos[-s[i]][1].pop_back();
int true_j=j-(neg-range(j,i-1));
ans+=true_i-true_j;
used[j]=true;
add_cn(j);
}
else{
assert(!max_pos[s[i]][0].empty());
int true_i=i-neg, j=max_pos[s[i]][0].back();
max_pos[s[i]][0].pop_back();
int true_j=j-(neg-range(j,i-1));
ans+=true_i-true_j-1;
used[j]=true;
add_cn(j);
}
neg++;
}
return ans;
}
