## 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月