ACOJ là một tổ chức quốc tế tập trung vào nghiên cứu hạt nhân và vật lý hạt. Hệ thống gia tốc hạt tại ACOJ được sử dụng để tiến hành các thí nghiệm liên quan đến va chạm của các hạt ở tốc độ cao.

Chúng ta xét \(N\) hạt được sắp xếp trong một dãy. Mỗi hạt được xác định bởi loại của nó \(v_i\), được biểu diễn bằng một số nguyên dương từ \(1\) đến \(N\).

Trong nghiên cứu mới nhất, cần phải tiến hành \(Q\) thí nghiệm. Trong thí nghiệm thứ \(i\), chúng ta quan sát tất cả các hạt từ hạt thứ \(l_i\) đến hạt thứ \(r_i\) trong dãy \((l_i \lt r_i)\). Trong số các hạt được quan sát, chúng ta có thể chọn hai hạt bất kỳ thuộc loại khác nhau và cho chúng va chạm trong máy gia tốc, khiến cả hai hạt bị phá hủy. Chúng ta lặp lại quá trình va chạm này miễn là còn hai hạt thuộc loại khác nhau trong số các hạt được quan sát. Thí nghiệm kết thúc khi tất cả các hạt được quan sát đã bị phá hủy hoặc khi chỉ còn lại một số hạt cùng loại. Tất nhiên, tùy thuộc vào thứ tự chúng ta cho các hạt va chạm, có thể kết thúc với nhiều loại hạt khác nhau.

Vì va chạm hạt không rẻ, bạn đã quyết định chỉ tiến hành thí nghiệm trong lý thuyết. Bây giờ, với mỗi thí nghiệm, bạn quan tâm đến có bao nhiêu loại hạt tồn tại sao cho có thể kết thúc thí nghiệm với một số hạt còn lại thuộc loại đó.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên dương \(N\) và \(Q\), số lượng hạt và số lượng thí nghiệm.
• Dòng tiếp theo chứa một dãy \(N\) số \(v_1, ..., v_n\), biểu diễn loại của các hạt.
• Trong mỗi dòng trong \(Q\) dòng tiếp theo, có một cặp hai số nguyên dương \(l_i\) và \(r_i\) \((1 \le l_i \lt r_i \le N)\), biểu diễn khoảng các hạt được quan sát trong thí nghiệm thứ \(i\).

Dữ liệu ra

• Với mỗi thí nghiệm trong \(Q\) thí nghiệm, in ra trên một dòng riêng số lượng loại hạt mà có thể kết thúc thí nghiệm với loại đó.

Chấm điểm

• Trong tất cả các subtask, \(2 \le N \le 500,000\) và \(1 \le Q \le 500,000\).

Input 1

11 5
2 4 2 3 4 4 3 1 4 4 4
1 4
2 8
6 9
8 10
8 11

Output 1

1
4
1
1
1

Giải thích ví dụ đầu tiên:

• Trong thí nghiệm đầu tiên, chúng ta có thể cho va chạm các hạt loại 3 và 4, để lại hai hạt loại 2. Không có cách nào để kết thúc với bất kỳ loại hạt nào khác.
• Trong thí nghiệm thứ hai, có thể kết thúc với một số hạt còn lại của mỗi loại.
• Trong thí nghiệm thứ tư và thứ năm, bất kể lựa chọn va chạm như thế nào, một số hạt loại 4 sẽ còn lại ở cuối.