Tý có một nhà nghiên cứu sinh học đang khảo sát sự đa dạng loài trên một dải rạn san hô dài \(N\) mét. Mỗi mét trên rạn san hô được ghi nhận mã số của một loài sinh vật biển (là một số nguyên dương). Nhà nghiên cứu muốn thực hiện \(Q\) truy vấn, mỗi truy vấn yêu cầu đếm số lượng loài khác nhau có mặt trên đoạn rạn san hô liên tiếp từ mét \(L\) đến mét \(R\).

Hãy viết chương trình giúp nhà nghiên cứu xử lý nhanh các truy vấn.

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

• Dòng đầu chứa hai số nguyên dương \(N\) và \(Q\) (\(1 \le N, Q \le 10^5\)).
• Dòng thứ hai chứa \(N\) số nguyên dương \(a_1, a_2, \dots, a_N\) — mã số loài tại mỗi mét (\(1 \le a_i \le 10^9\)).
• \(Q\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(L_i, R_i\) (\(1 \le L_i \le R_i \le N\)).

Định dạng đầu ra

• In ra \(Q\) dòng, dòng thứ \(i\) là số loài khác nhau trong đoạn \([L_i, R_i]\).

Ví dụ

Input:

8 3
1 2 1 3 2 1 4 5
2 5
1 4
3 7

Output:

3
3
4

Giải thích:

• Đoạn \([2,5]\): \(\{2,1,3,2\}\) có 3 loài \(\{1,2,3\}\).
• Đoạn \([1,4]\): \(\{1,2,1,3\}\) có 3 loài \(\{1,2,3\}\).
• Đoạn \([3,7]\): \(\{1,3,2,1,4\}\) có 4 loài \(\{1,2,3,4\}\).

Subtask