// Problem 1008: 2D dominance counting (n = 1e7)
// Baseline: bucket sort by x (linked list) + Fenwick tree on y.
#include <cstring>
static int head[10000000];
static int nxt[10000000];
static unsigned tree[10000001];
extern "C" void count_2d(int n, const unsigned *x, const unsigned *y, unsigned *out) {
memset(head, 0xFF, sizeof(head));
for (int i = 0; i < n; ++i) {
nxt[i] = head[x[i]];
head[x[i]] = i;
}
for (int xi = 0; xi < n; ++xi) {
int i = head[xi];
if (i < 0) continue;
for (; i != -1; i = nxt[i]) {
unsigned s = 0;
for (unsigned j = y[i]; j; j &= j - 1) s += tree[j];
out[i] = s;
}
for (i = head[xi]; i != -1; i = nxt[i]) {
for (unsigned j = y[i] + 1; j <= (unsigned)n; j += j & -j) tree[j]++;
}
}
}