#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define sz(x) ((int)x.size())
ll tree[1000*1000];
ll lazy[1000*1000];
void update(int l, int r, int L, int R, int i, ll val) {
if(r < l || l > R || r < L) return;
if(L <= l && r <= R) {
tree[i] += lazy[i] + val;
lazy[2*i+1] += lazy[i] + val;
lazy[2*i+2] += lazy[i] + val;
lazy[i] = 0;
return;
}
lazy[2*i+1] += lazy[i];
lazy[2*i+2] += lazy[i];
lazy[i] = 0;
update(l, (l+r)/2, L, R, 2*i+1, val);
update((l+r)/2+1, r, L, R, 2*i+2, val);
tree[i] = tree[2*i+1] + tree[2*i+2];
}
ll sum(int l, int r, int L, int R, int i) {
if(r < l || l > R || r < L) return 0;
if(L <= l && r <= R) {
tree[i] += lazy[i];
lazy[2*i+1] += lazy[i];
lazy[2*i+2] += lazy[i];
lazy[i] = 0;
return tree[i];
}
lazy[2*i+1] += lazy[i];
lazy[2*i+2] += lazy[i];
tree[i] += lazy[i];
lazy[i] = 0;
return sum(l, (l+r)/2, L, R, 2*i+1) + sum((l+r)/2+1, r, L, R, 2*i+2);
}
ll count_swaps(vector<int> S) {
int n = (int)S.size();
ll ans = 0;
vector<deque<int>> L(n+1), R(n+1);
// vector<ll> avant(n+1,0);
// for(int i = 0; i < n; ++i)
// avant[i] = n - i - 1;
memset(tree, 0, sizeof(tree));
for(int i = 0; i < n; ++i)
update(0, n-1, i, i, 0, n-i-1);
for(int i = 0; i < n; ++i) {
// cout << "----" << endl;
// for(int i = 0; i < n; ++i) cout << avant[i] << " ";
// cout << endl;
// for(int i = 0; i < n; ++i) cout << sum(0, n-1, i, i, 0) << " ";
// cout << endl;
int x = abs(S[i]);
if(S[i] > 0) {
if(sz(L[x]) > 0) {
int j = L[x].front();
// ans += avant[j] - avant[i] - 1LL;
// for(int k = j + 1; k <= i; ++k)
// avant[k]--;
ans += sum(0, n-1, j, j, 0) - sum(0, n-1, i, i, 0) - 1LL;
update(0, n-1, j+1, i, 0, -1);
L[x].pop_front();
}
else R[x].push_back(i);
}
else {
if(sz(R[x]) > 0) {
int j = R[x].front();
// ans += avant[j] - avant[i];
// for(int k = j; k <= i; ++k)
// avant[k]--;
ans += sum(0, n-1, j, j, 0) - sum(0, n-1, i, i, 0);
update(0, n-1, j, i, 0, -1);
R[x].pop_front();
}
else L[x].push_back(i);
}
}
return ans;
}
