Cho dãy số \(A\) gồm \(n\) phần tử \(a_1, a_2... a_n\) và \(q\) truy vấn. Mỗi truy vấn có dạng \((l,r)\) yêu cầu bạn phải trả về số lượng phần tử phân biệt trong đoạn vị trí \([l,r]\) của dãy \(A\).

Yêu cầu

• Hãy trả lời các truy vấn và đưa ra đáp án?

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên dương \(n\)
• Dòng thứ hai chứa \(n\) số nguyên dương \(a_1, a_2... a_n\)
• Dòng thứ ba chứa số nguyên dương \(q\)
• Trên \(q\) dòng tiếp theo, mỗi dòng chứa một cặp số nguyên dương \(l,r\) thể hiện một truy vấn.

Ràng buộc

• \(1 \le n \le 30000\)
• \(1 \le a_i \le 10^6\)
• \(1 \le q \le 2 \times 10^5\)

Dữ liệu ra

• Với mỗi truy vấn, in ra kết quả trên một dòng.

Input 1

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

Output 1

3
2
3