Bài 4: Truy vấn (5.0 điểm)

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

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

Input

Đọc từ tệp CAU4.INP gồm:

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

Các số trên một dòng cách nhau bởi dấu cách.

Output

Ghi ra tệp CAU4.OUT. Mỗi truy vấn ghi ra một dòng là kết quả của truy vấn đó theo đúng thứ tự input.

Input

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

Output

%
6
5
3
2

Scoring

• 30% số điểm với \(n \le 10^4,\ q \le 10^4\);
• 30% số điểm với \(n \le 10^4,\ q \le 10^5\);
• 40% số điểm với \(n \le 10^5,\ q \le 10^5\).