#include "shoes.h"
#include <iostream>
#include <string>
#include <set>
#include <map>
#include <cstring>
#include <unordered_map>
#include <vector>
#include <fstream>
#include <bitset>
#include <tuple>
#include <cmath>
#include <cstdint>
#include <stack>
#include <cassert>
#include <cstdio>
#include <queue>
#include <iterator>
#include <iomanip>
#include <algorithm>
#include <sstream>
#define INF 9223372036854775801
#define int long long
#define double long double
#define MOD(a) ((a) % 1000000007 + 1000000007 ) % 1000000007
#define F first
#define caseOut(t) cout << "Case " << t << ": ";
#define S second
#define USACO_SETUP() ifstream cin("paint.in"); ofstream cout("paint.out");
#define SETUP() ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
struct node {
node* left, * right;
int sum;
int lazy = 0;
void update() {
sum = left->sum + right->sum;
}
};
void propagate(node *root, int left, int right) {
if (root->lazy != 0) {
root->sum += (left - right + 1) * root->lazy;
if (left != right) {
root->left->lazy += root->lazy;
root->right->lazy += root->lazy;
}
}
root->lazy = 0;
}
int query(node* root, int x, int left, int right) {
propagate(root, left, right);
if (left == right) return root->sum;
if (x > right || x < left) return 0;
int mid = (left+right)/2;
if (x <= mid) return query(root->left, x, left, mid);
else return query(root->right, x, mid + 1, right);
}
void update(node* root, int x, int uLeft, int uRight, int left, int right) {
propagate(root, left, right);
if (right<uLeft || left>uRight) return;
if (right <= uRight && left >= uLeft) {
root->lazy = x;
propagate(root, left, right);
return;
}
int mid = (left + right) / 2;
update(root->left, x, uLeft, uRight, left, mid);
update(root->right, x, uLeft, uRight, mid+1, right);
root->update();
}
void build(node* root, int left, int right) {
if (left == right) {
root->sum = 0;
return;
}
int mid = (left + right) / 2;
root->left = new node{ NULL, NULL, 0 };
root->right = new node{ NULL, NULL, 0 };
build(root->left, left, mid);
build(root->right, mid + 1, right);
root->sum=0;
}
long long count_swaps(std::vector<signed> s) {
int n = s.size();
vector<int> prefx(n);
vector<bool> uncount(n);
int i = 0;
node* root = new node{ NULL, NULL, 0 };
build(root, 0, n-1);
map<int, queue<int>> mp;
int sum = 0;
for (int i = 0; i < n; i++) mp[s[i]].push(i);
for (auto u : mp)
{
while (!u.second.empty()) {
int a = u.second.front();
int b=mp[-u.first].front();
if (b < a) swap(a, b);
u.second.pop();
mp[-u.first].pop();
prefx[a] = b;
prefx[b] = a;
uncount[b] = true;
}
}
for (int i = 0; i < n; i++)
{
if (uncount[i]) continue;
int a = i;
int b = prefx[a];
int posA = query(root, a, 0, n - 1)+a;
int posB= query(root, b, 0, n - 1)+b;
int dist = (s[a] < 0) ? (posB - posA - 1) : (posB - posA);
sum += dist;
if (b - a > 1) update(root, 1, a + 1, b - 1, 0, n - 1);
}
return sum;
}
