How to solve following range query problem (Related to DIFVAL)?

problem
How to find number of distinct integers between two indices of an array online (without sorting the queries)?

I thought of solving above for 24 points in DIFVAL but i did not came up with any idea .We cannot sort the queries since answer obtained for first query decides conditions for second query . If we can solve by sorting please tell.

Read the comments…you’ll find the answer.

Persistent segment trees or merge sort trees can be used to solve this kind of question.

Its a well known problem named DQUERY
DQUERY
In DQUERY we can process queries offline but in this question we have to process it online.
You can search for Dquery spoj online and you can get well written code for the problem.