Count points in 2-d range
First, notice that it is enough to compute how many elements in $a_1,\ldots,a_E$ are less than $X$. (Why?)

Second, assume for simplicity that $N$ is a power of 2. We partition $\{1,\ldots,N\}$ into intervals in $\log N$ ways: as a single interval of length $N$, two intervals of length $N/2$, four intervals of length $N/4$, and so on. We sort each of these. This takes time $O(N\log^2 N)$. (Why?)

Third, given $E$ and $X$, write $a_1,\ldots,a_E$ as a sum of $O(\log N)$ intervals  of the kind we sorted above (use the binary expansion of $E-1$). Find the correct count for each of them in time $O(\log N)$ by searching for $X$ in the sorted interval, and compute the sum.