{assign var="code" value="DQUERY"} {if $par==""} {assign var=par value=$locale} {/if}

{if $par=="vn"} {literal}

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.

Dữ liệu

• Dòng 1: n (1 ≤ n ≤ 30000).
• Dòng 2: n số a₁, a₂, ..., a_n (1 ≤ a_i ≤ 10⁶).
• 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.

   

Ví dụ

Dữ liệu
5
1 1 2 1 3
3
1 5
2 4
3 5

Kết quả
3
2
3 

{/literal}{elseif ($par=="en" || $par=="")}{literal}

Given a sequence of n numbers a₁, a₂, ..., a_n and a number of d-queries. A d-query is a pair (i, j) (1 ≤ i ≤ j ≤ n). For each d-query (i, j), you have to return the number of distinct elements in the subsequence a_i, a_i+1, ..., a_j.

Input

• Line 1: n (1 ≤ n ≤ 30000).
• Line 2: n numbers a₁, a₂, ..., a_n (1 ≤ a_i ≤ 10⁶).
• Line 3: q (1 ≤ q ≤ 200000), the number of d-queries.
• In the next q lines, each line contains 2 numbers i, j representing a d-query (1 ≤ i ≤ j ≤ n).

Output

• For each d-query (i, j), print the number of distinct elements in the subsequence a_i, a_i+1, ..., a_j in a single line.

   

Example

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

Output
3
2
3 

{/literal} {/if}