You are given an array $A$ of size N $(N\leq 1\,000\,000)$ containing all integers $1..N$ exactly once. You are required to answer query in $O(\log^2 N )$ and to preprocess in $O(N\log^2N)$:
How many elements are there between indexes S and E, that are less than X? $( |L| : \forall l \in L \leftrightarrow A[l] < X \bigwedge S\leq l \leq E )$
$X, S, E$ will vary from query to query, and there will be at most $1\,000\,000$ queries.
I found a lot of algorithms based on kd-trees, but they have complexity linear in the size of the output. Are there any other options, maybe using the property that X and Y coordinates are unique?