提示: 欢迎访问OurACM平台。
Problem 1656 How many different numbers

Accept: 194    Submit: 1408
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

Recently oaiei has encountered a problem. And he needs your help.
There are N numbers in an array and Q queries. For each query, there are two integers S and T. And the proplem is that there are how many different numbers in the index range [S,T] of the array (the array ‘s index is started from 1).

Input

There are multiple test cases. For each test case, the first line is an integer N (1<=N<=100000), indicating there are N numbers in the array. In the second line,there are N integers which are separated by a space. The third line is an integer Q(1<=Q<=1000), indicating there are Q queries. The following Q lines, for each line, there are two integers S and T(1<=S<=T<=N), indicating the index range of the array. The element value of the array will fit in a signed 32-bit integer.

Output

For each test, output an integer, indicating the number of different numbers in the index range [S,T] of the array.

Sample Input

10 1 2 3 3 3 3 4 -9 -9 10 2 1 5 5 10

Sample Output

3 4

Source

FOJ月赛-2008年10月

Submit  Back  Status  Discuss