Cho dãy số nguyên dương gồm ~n~ số hạng ~a_1, a_2, ..., 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 \le l_{i} \le r_{i} \le n;\ 1 \le i \le q)~, hãy trả lời trong đoạn con ~a_l, a_{l + 1}, ..., a_r~ có bao nhiêu số hạng khác nhau.

Dữ liệu đầu vào

Gồm ~q + 3~ dòng:

• 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, ..., a_n~ ~(1 \le a_i \le 10^9;\ i = 1, 2, ..., n)~.
• 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;\ i = 1, 2, ..., q)~ tương ứng với một truy vấn.

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

Dữ liệu đầu ra

Tương ứng với mỗi truy vấn theo thứ tự từ dữ liệu vào ghi ra một dòng gồm một số là kết quả tìm được của truy vấn đó.

Ràng buộc dữ liệu

• Có 30% số điểm có ~n \le 10^4;\ q \le 10^4~.
• Có 30% số điểm có ~n \le 10^4;\ q \le 10^5~.
• Có 40% số điểm có ~n \le 10^5;\ q \le 10^5~.

Ví dụ

Ví dụ 1

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