// Problem 1008: 2D dominance counting (n = 1e7)
// Counting sort by x (O(n)) + Fenwick tree on y.
#include <cstring>
static int cnt[10000000];
static int order[10000000];
static unsigned tree[10000001];
void count_2d(int n, const unsigned *x, const unsigned *y, unsigned *out) {
// counting sort by x: cnt[] zeroed (static bss); order[] built in x-ascending
for (int i = 0; i < n; ++i) cnt[x[i]]++;
for (int i = 1; i < n; ++i) cnt[i] += cnt[i - 1];
for (int i = 0; i < n; ++i) order[--cnt[x[i]]] = i;
// sweep in x order; within one x-bucket: query all, then update all
int k = 0;
while (k < n) {
unsigned cur_x = x[order[k]];
int kk = k + 1;
while (kk < n && x[order[kk]] == cur_x) kk++;
for (int t = k; t < kk; ++t) {
int i = order[t];
unsigned s = 0;
for (unsigned j = y[i]; j; j &= j - 1) s += tree[j];
out[i] = s;
}
for (int t = k; t < kk; ++t) {
int i = order[t];
for (unsigned j = y[i] + 1; j <= (unsigned)n; j += j & -j) tree[j]++;
}
k = kk;
}
}