#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 4e5 + 6e3;
int n;
vector<int> positions[MAXN];
int szz[MAXN];
inline int code(int val){
return (val < 0 ? -val : val + 200000);
}
struct SegTree{
int size = 1;
struct node{
int val = 0;
bool isAdded = false;
int AddedValue = 0;
node(int x, bool y, int z){
val = x, isAdded = y, AddedValue = z;
}
node(){};
};
vector<node> tree;
bool flag;
void build(int v, int tl, int tr, vector<int>&a){
if (tl == tr){
tree[v].val = (!flag ? 1 : tl < a.size() ? a[tl] : 0);
return;
}
int tm = (tl + tr) >> 1;
build(v + v + 1, tl, tm, a);
build(v + v + 2, tm + 1, tr, a);
tree[v].val = tree[v + v + 1].val + tree[v + v + 2].val;
}
void init(vector<int>&a, bool _flag){
flag = _flag;
while (size <= a.size()) size <<= 1;
tree.resize(2 * size);
build(0, 0, size - 1, a);
}
void propagate(int v, int tl, int tr){
if (!tree[v].isAdded || tl == tr) return;
int tm = (tl + tr) >> 1;
tree[v + v + 1].val += tree[v].AddedValue * (tm - tl + 1);
tree[v + v + 1].AddedValue += tree[v].AddedValue;
tree[v + v + 2].val += tree[v].AddedValue * (tr - tm);
tree[v + v + 2].AddedValue += tree[v].AddedValue;
tree[v + v + 1].isAdded = tree[v + v + 2].isAdded = true;
tree[v].isAdded = false;
tree[v].AddedValue = 0;
}
void Range_Add(int v, int tl, int tr, int l, int r, int val){
if (l <= tl && tr <= r){
tree[v].isAdded = true;
tree[v].val += (tr - tl + 1) * val;
tree[v].AddedValue += val;
return;
}
if (tl > r || tr < l) return;
propagate(v, tl, tr);
int tm = (tl + tr) >> 1;
Range_Add(v + v + 1, tl, tm, l, r, val);
Range_Add(v + v + 2, tm + 1, tr, l, r, val);
tree[v].val = tree[v + v + 1].val + tree[v + v + 2].val;
}
void Range_Add(int l, int r, int val){
Range_Add(0, 0, size - 1, l, r, val);
}
void update(int v, int tl, int tr, int pos, int val){
if (tl == tr){
tree[v].val = val;
return;
}
int tm = (tl + tr) >> 1;
if (pos <= tm) update(v + v + 1, tl, tm, pos, val); else
update(v + v + 2, tm + 1, tr, pos, val);
tree[v].val = tree[v + v + 1].val + tree[v + v + 2].val;
}
void update(int pos, int val){
update(0, 0, size - 1, pos, val);
}
pair<int, int> find_kth(int v, int tl, int tr, int k){
if (tl == tr) return make_pair(tree[v].val, tl);
int tm = (tl + tr) >> 1;
if (tree[v + v + 1].val >= k) return find_kth(v + v + 1, tl, tm, k); else
return find_kth(v + v + 2, tm + 1, tr, k - tree[v + v + 1].val);
}
pair<int, int> find_kth(int k){
return find_kth(0, 0, size - 1, k);
}
int get(int v, int tl, int tr, int l, int r){
if (l <= tl && tr <= r) return tree[v].val;
if (tl > r || tr < l) return 0;
propagate(v, tl, tr);
int tm = (tl + tr) >> 1;
return get(v + v + 1, tl, tm, l, r) + get(v + v + 2, tm + 1, tr, l, r);
}
int get(int l, int r){
return get(0, 0, size - 1, l, r);
}
int get(int pos){
return get(pos, pos);
}
};
SegTree st[MAXN];
long long count_swaps(vector<int> a) {
n = a.size();
vector<int> perm(n);
for (int i = 0; i < n; i++){
positions[code(a[i])].push_back(i);
perm[i] = i;
}
st[0].init(perm, true);
for (int i = 1; i < MAXN; i++){
st[i].init(positions[i], false);
szz[i] = positions[i].size();
}
vector<bool> used(n, false);
ll ans = 0;
for (int i = 0; i < n; i++){
if (used[i]) continue;
int x = code(a[i]), y = code(-a[i]);
int pos1 = st[0].get(i), pos2 = -1;
int index1 = st[x].find_kth(1).second, index2 = 0;
int l = 1, r = szz[y];
while (l <= r){
int mid = (l + r) >> 1;
pair<int, int> p = st[y].find_kth(mid);
//cout << p.second << endl;
int ind = positions[y][p.second];
if (st[0].get(ind) >= pos1){
pos2 = ind;
index2 = p.second;
r = mid - 1;
} else l = mid + 1;
}
//cout << pos1 << ' ' << pos2 << endl;
//cout << index1 << ' ' << index2 << endl;
st[x].update(index1, 0);
st[y].update(index2, 0);
szz[x]--;
szz[y]--;
ans += pos2 - pos1 - 1 + (a[i] > 0);
used[positions[y][index2]] = true;
st[0].Range_Add(index1 + 1, index2 - 1, 1);
}
return ans;
}
