Nguồn đề : https://www.spoj.com/problems/DQUERY/vn/

Có thể nộp thêm ở link trên để kiểm chứng solution của mình

Cho một dãy số n phần tử ~a_1, a_2, ..., a_n~ và một số các truy vấn-d. Một truy vấn-d là một cặp (i, j) (1 ≤ i ≤ j ≤ n). Với mỗi truy vấn-d (i, j), bạn cần trả về số phần tử phân biệt nằm trong dãy con ~ a_i, a_{i+1}, ..., a_j~.

Input

Dòng 1: n (1 ≤ n ≤ 30000).

Dòng 2: n số ~ a_1, a_2, ..., a_n (1 ≤ a_i ≤ 10^6).~

Dòng 3: q (1 ≤ q ≤ 200000), số lượng truy vấn- d.

Trong q dòng sau, mỗi dòng chứa 2 số i, j biểu thị một truy vấn-d (1 ≤ i ≤ j ≤ n).

Kết quả

Với mỗi truy vấn-d (i, j), in ra số phần tử phân biệt thuộc dãy con ~ a_i, a_{i+1}, ..., a_j~ trên một dòng.

Sample Input

5
1 1 2 1 3
3
1 5
2 4
3 5

Sample Output

3
2
3