DQUERY Truy vấn d

Cho một dãy số n phần tử a₁, a₂, ..., 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: ghi số ngyên dương n (1 ≤ n ≤ 30000).
• Dòng 2: ghi n số nguyên dương a₁, a₂, ..., a_n (1 ≤ a_i ≤ 10⁶).
• Dòng 3: ghi số q là số lượng truy vấn- d (1 ≤ q ≤ 200000).
• 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).

Output: 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.

Input	Output
5 1 1 2 1 3 3 1 5 2 4 3 5	3 2 3