Difficulty in understanding an approach to SPOJ $d$-query problem
(This answer is no longer very interesting, now that the question has been corrected to clarify that $1 \le a_i \le 10^6$ instead of $1 \le a_i \le 106$.)

This can be solved in $10^6(n+q)$ operations.

First, build a table $T[\cdot,\cdot]$, where $T[j,x]$ is the index of the last occurrence of the number $x$ among $a_1,a_2,\dots,a_j$.  In other words,

$$T[j,x] = \max \{i : a_i=x \wedge 1\le i\le j\}.$$

This table can be built in $10^6n$ steps.

Next, you should be able to see how to answer a query $(i,j)$ quickly, by doing some lookups into the $T$ table.  I'll let you work out the details so you can have the fun of solving the problem.