#include "shoes.h"
#include <algorithm>
#include <bitset>
#include <cstdint>
#include <cstring>
#include <iostream>
#include <limits.h>
#include <math.h>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#define int long long
#define loop(X, N) for(int X = 0; X < (N); X++)
#define all(V) V.begin(), V.end()
#define rall(V) V.rbegin(), V.rend()
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vector<ii>> vvii;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;
struct SegTree {
int n, N;
vi tree;
SegTree(const vi& values) {
n = values.size();
N = 1;
while (N < n) N *= 2;
tree = vi(2 * N);
loop(i, n) {
tree[N + i] = values[i];
}
for (int i = N - 1; i >= 1; i--) {
tree[i] = tree[2 * i] + tree[2 * i + 1];
}
}
void set(int idx, int v, int i = 1, int tl = 0, int tr = -1) {
if (tr == -1) {
tr = N;
}
if (tr - tl == 1) {
tree[i] = v;
return;
}
int tm = (tl + tr) / 2;
if (idx < tm) {
set(idx, v, 2 * i, tl, tm);
}
else {
set(idx, v, 2 * i + 1, tm, tr);
}
tree[i] = tree[2 * i] + tree[2 * i + 1];
}
int get(int idx) {
return tree[N + idx];
}
int getRange(int l, int r, int i = 1, int tl = 0, int tr = -1) {
if (tr == -1) {
tr = N;
}
if (tr <= l || tl >= r) {
return 0;
}
if (tl >= l && tr <= r) {
return tree[i];
}
int tm = (tl + tr) / 2;
return getRange(l, r, i * 2, tl, tm) + getRange(l, r, i * 2 + 1, tm, tr);
}
};
long long count_swaps(std::vector<signed> s) {
int n = s.size();
vector<pair<vi, vi>> positions(n);
loop(i, n) {
if (s[i] < 0) {
positions[-s[i]].first.push_back(i);
}
else {
positions[s[i]].second.push_back(i);
}
}
vii ptrs(n);
int result = 0;
SegTree isUsed(vi(n, false));
for (int i = 0; i < n; i++) {
if (isUsed.get(i)) continue;
int v = s[i];
int next;
if (v < 0) {
next = positions[-v].second[ptrs[-v].second];
ptrs[-v].first++;
ptrs[-v].second++;
}
else {
next = positions[v].first[ptrs[v].first];
ptrs[v].first++;
ptrs[v].second++;
}
int count = (next - i - 1) - isUsed.getRange(i + 1, next + 1);
// for (int j = i + 1; j < n; j++) {
// if (s[j] == -v && !isUsed.get(j)) {
// isUsed.set(j, true);
// break;
// }
// count += 1 - isUsed.get(j);
// }
if (v < 0) {
result += count;
}
else {
result += count + 1;
}
isUsed.set(next, true);
isUsed.set(i, true);
}
return result;
}
