C++: Remove repeated elements and give a Range Sum

I have a question regarding already asked this question: SPOJ DQUERY : TLE Even With BIT?

What if I would like to not consider the repeated element to count when I make a range query? following is an example:

Input

Line 1: n (1 ≤ n ≤ 10^6).
Line 2: n numbers a1, a2, ..., an (-10^9 ≤ ai ≤ ).
Line 3: q (1 ≤ q ≤ 10^6), the number of d-queries.
In the next q lines, each line contains 2 numbers i, j 
representing a d-query (1 ≤ i ≤ j ≤ n).

Output

For each d-query (i, j), print the number of distinct elements in the 
subsequence ai, ai+1, ..., aj in a single line.
Example

Input
9
1 2 3 2 4 1 2 3 4
3
1 9
2 4
5 9
2 7

Output
0          //Explanation: all elements have been repeated.
1          //Explanation: only 3 has not repeated.
3          //Explanation: only 4 is repeated, so count only 1, 2 and 3.
3          //Explanation: only 2 is repeated, so count only 3, 4 and 1.

what could it be the necessary changes which should have done in @kraskevich 's answer(which is an efficient solution for that particular case)? I tried to add 0 in BIT, instead of -1 in above-mentioned solution, which does not help for all types of queries. Can anybody get me an idea?