import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
public class shoes {
private int[] tree;
private void add(int from, int to, int a, int b, int node) {
if (from <= a && b <= to) {
tree[node]++;
return;
}
int mid = (a + b) / 2;
if (from <= mid) {
add(from, to, a, mid, node * 2);
}
if (to > mid) {
add(from, to, mid + 1, b, node * 2 + 1);
}
}
private int getSum(int i, int a, int b, int node) {
if (a == b) {
return tree[node];
}
int mid = (a + b) / 2;
if (i <= mid) return getSum(i, a, mid, node * 2) + tree[node];
return getSum(i, mid + 1, b, node * 2 + 1) + tree[node];
}
public long count_swaps(int[] s) {
int n = s.length;
ArrayDeque<Integer>[] shoes = new ArrayDeque[2 * n + 1];
for (int i = 0; i <= 2 * n; i++) shoes[i] = new ArrayDeque<Integer>();
for (int i = 0; i < n; i++) {
shoes[s[i] + n].addLast(i);
}
tree = new int[4 * n];
long swaps = 0;
for (int i = 0; i < n; i++) {
if (shoes[n + s[i]].isEmpty() || shoes[n + s[i]].peekFirst() != i) continue;
//System.out.println(i);
int index1 = getSum(i, 0, n - 1, 1) + i;
shoes[n + s[i]].removeFirst();
int orgIndex2 = shoes[n - s[i]].removeFirst();
int index2 = getSum(orgIndex2, 0, n - 1, 1) + orgIndex2;
swaps += index2 - index1;
if (s[i] < 0) swaps--;
add(0, orgIndex2, 0, n - 1, 1);
}
return swaps;
}
}
