Finding the number of $L\leq j\leq R$ such that $a[j] \leq a[i]$
Here is a solution in time $O((Q+n)\log^2 n)$ and space $O(n\log n)$. For simplicity, assume that $n$ is a power of $2$, and that the array is zero-based.

A dyadic interval is an interval of the form $[c \cdot 2^k,(c+1) \cdot 2^k)$ (that is, $c\cdot 2^k,\ldots,(c+1)\cdot 2^k-1$). For example, when $n = 8$ we have the following dyadic intervals:
$$
[0,8),[0,4),[4,8),[0,2),[2,4),[4,6),[6,8), \\
[0,1),[1,2),[2,3),[3,4),[4,5),[5,6),[6,7),[7,8).
$$
Each interval of the form $[0,x)$ is the disjoint union of at most $\log_2 n$ slices. For example, for $n = 8$ we have (for $x \neq 1,2,4,8$):
$$
[0,3) = [0,2) \cup [2,3),  \\
[0,5) = [0,4) \cup [4,5), \\
[0,6) = [0,4) \cup [4,6), \\
[0,7) = [0,4) \cup [4,6) \cup [6,7).
$$

A dyadic slice of the array $a$ consists of the elements $a[s],\ldots,a[t]$ for some dyadic interval $s,\ldots,t$.

As preprocessing, we sort (separately) each dyadic slice of $a$. This takes time $O(n\log^2 n)$ and consumes space $O(n\log n)$ (since each index participates in $\log_2 n$ slices).

As mentioned in the question, it is enough to handle the following type of query:


  Given $i,R$, count the number of indices $j &lt;R$ such that $a[j] \leq a[i]$. 


Given $i,R$, we retrieve $a[i]$, and present $[0,R)$ as a union of $O(\log n)$ dyadic intervals $I_1,\ldots,I_m$. Using binary search, for each $k$ we determine the number of indices $j \in I_k$ such that $a[j] \leq a[i]$. This takes time $O(\log^2 n)$ (altogether). Summing these numbers, we arrive at the answer to the query.