Tý có mảng \(A\) gồm N số nguyên. Bạn cần thực hiện Q truy vấn, mỗi truy vấn yêu cầu đếm số lượng giá trị khác nhau (phân biệt) trong khoảng từ chỉ số l đến chỉ số \(r\) của mảng.

Ví dụ

Input:

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

Output:

2
3
3

Ràng buộc

Định dạng đầu vào

• Dòng đầu chứa hai số nguyên \(N\) và Q (\(1 \le N, Q $\le 10^5\)).
• Dòng hai chứa \(N\) số nguyên \(a_1, a_2, \dots, a_N\) (\(1 \le a_i $\le 10^9\)).
• Q$ dòng tiếp theo, mỗi dòng chứa hai số \(l, r\) (\(1 \le l \le r $\le N\)).

Định dạng đầu ra

• In ra kết quả cho mỗi truy vấn trên một dòng riêng.