Distinct Numbers

You are given an array with N numbers. Your aim is to find the number of distinct numbers in the index range L to R for each of the Q queries. Input N A1 A2 . . . . . . .AN Q L1 R1 L2 R2 . . . . LQ RQ Output Print the answer for each query on a newline Constraints - 1 ≤ N,Q ≤ 106 - 1 ≤ L ≤ R ≤ N - 0 ≤ Ai ≤ 109 Example 1 10 1 1 2 3 4 4 5 6 7 1 1 1 10 Answer 7 since there are seven disti