Không Có Thời Gian Chờ Khô

Có $N$ đoạn hàng rào liên tiếp, mỗi đoạn cần được sơn một màu nhất định. Màu được đánh số từ $1$ đến $N$ theo thứ tự độ đậm tăng dần (màu $1$ nhạt nhất, màu $N$ đậm nhất). Ban đầu tất cả các đoạn chưa được sơn màu nào.

Một nét sơn có thể sơn một đoạn liên tiếp bất kỳ với một màu duy nhất, với điều kiện không được sơn màu nhạt hơn lên vùng đã có màu đậm hơn (chỉ được sơn màu đậm hơn lên màu nhạt hơn, không được ngược lại).

Có $Q$ truy vấn độc lập với nhau. Mỗi truy vấn cho một đoạn $[a,b]$: hỏi cần ít nhất bao nhiêu nét sơn để hoàn thành màu cho tất cả các đoạn trong $[a,b]$ đúng như yêu cầu, trong khi không sơn vào bất kỳ đoạn nào ngoài $[a,b]$?

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên $N$ và $Q$.

Dòng thứ hai chứa $N$ số nguyên $c_1,c_2,\dots ,c_N$ — màu mong muốn của từng đoạn hàng rào.

• $Q$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $a$ và $b$ mô tả một truy vấn.

Dữ liệu ra

Với mỗi truy vấn, in ra một số nguyên duy nhất trên một dòng.

Ràng buộc

• $1\le N,Q\le 2\times {10}^5$
• $1\le c_i\le N$
• $1\le a\le b\le N$

Ví dụ

Ghi chú

Mỗi truy vấn được xử lý độc lập — kết quả của truy vấn này không ảnh hưởng đến truy vấn khác.