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_i, r_i$ ($1 \leq l_i \leq r_i \leq n, 1 \leq i \leq q$) hãy trả lời trong đoạn con $a_{l[i]}, a_{l[i + 1]}, \ldots a_{r[i]}$ có bao nhiêu số hạng khác nhau.

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, \ldots, a_n$ ($1 \leq a_i \leq 10^9, i = 1, 2, ..., 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 dương $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 dấu cách.

Kết quả ghi ra tệp văn bản CAU4.OUT Tương ứng với mỗi truy vấn theo thứ tự từ tệp 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 đó.

Chấm điểm:

• $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$.

Ví dụ:

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

6
5
3
2