Truy vấn

Cho dãy số nguyên dương gồm \(n\) số hạng \(a_1, a_2, \dots, a_n\).

Yêu cầu: Có \(q\) truy vấn, mỗi truy vấn gồm hai chỉ số \(l_i, r_i\) \((1 \leq l_i \leq r_i \leq n, 1 \leq i \leq q)\) yêu cầu trả lời trong đoạn con \(a_{l_i}, a_{l_i+1}, \dots, a_{r_i}\) có bao nhiêu số hạng khác nhau.

Input

Dữ liệu vào từ tệp văn bản CAU4.INP gồm:

• Dòng đầu tiên chứa số nguyên \(n\) \((1 \leq n \leq 10^5)\).
• Dòng thứ hai chứa \(n\) số nguyên dương \(a_1, a_2, \dots, a_n\) \((1 \leq a_i \leq 10^9, 1 \leq i \leq n)\).
• Dòng thứ ba chứa số nguyên \(q\) \((1 \leq q \leq 10^5)\).
• \(q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(l_i, r_i\) \((1 \leq l_i \leq r_i \leq n, 1 \leq i \leq q)\) tương ứng với một truy vấn.

Các số trên một dòng cách nhau đúng một dấu cách.

Output

Ghi ra tệp văn bản CAU4.OUT gồm:

• Tương ứng với mỗi truy vấn, in ra một dòng chứa một số là kết quả của truy vấn đó.

Example

9
33 5 6 7 8 112 6 6 6
4
1 9
2 7
5 9
3 4

6
5
3
2

Scoring

• 30% số điểm có \(n \leq 10^4, q \leq 10^4\).
• 30% số điểm có \(n \leq 10^4, q \leq 10^5\).
• 40% số điểm có \(n \leq 10^5, q \leq 10^5\).