Giá Trị Khác Nhau

Cho một dãy gồm $n$ số nguyên dương. Mỗi truy vấn chọn một đoạn liên tiếp từ vị trí $l$ đến vị trí $r$ (tính cả hai đầu). Trong một đoạn, một giá trị dù xuất hiện nhiều lần cũng chỉ được tính một lần. Với mỗi truy vấn, hãy xác định số giá trị khác nhau có mặt trong đoạn được chọn.

Input

• Dòng đầu chứa số nguyên $n$ - số phần tử của dãy.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$.
• Dòng thứ ba chứa số nguyên $q$ - số truy vấn.
• Mỗi trong $q$ dòng tiếp theo chứa hai số nguyên $l$ và $r$.

Output

• Với mỗi truy vấn, in trên một dòng số giá trị khác nhau trong đoạn $a_l,a_{l+1},\dots ,a_r$.

Constraints

• $1\le n\le 3\cdot 10^4$.
• $1\le a_i\le 10^6$ với mọi $i$.
• $1\le q\le 2\cdot 10^5$.
• $1\le l\le r\le n$ với mọi truy vấn.

Scoring

• Subtask $1$ ($50\%$ số điểm): $n\le 2000$ và $q\le 5000$.
• Subtask $2$ ($50\%$ số điểm): Không có giới hạn bổ sung.

Example

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

4
3
1
4