Cho 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.

Đị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.

Ví dụ

Input:

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

Output:

2
3
3