San Hà Xã Tắc Đồ

Tương truyền, San Hà Xã Tắc Đồ là một pháp bảo vô cùng cường đại do Nữ Oa nương nương thời thượng
cổ lưu lại. Uy lực của bức họa này có thể tạo dựng cả một thế giới riêng -- thiên địa sinh thành, nhật nguyệt vận hành, vạn vật hữu linh đều có thể hiện ra trong tranh. Ai nắm giữ được bức họa, chẳng khác nào nắm giữ một cõi thế giới riêng biệt trong lòng bàn tay.

Lâm là một đạo sĩ đã tu luyện đến cảnh giới gần kề thánh nhân, trong một lần cơ duyên gặp gỡ, tìm được một bức họa cổ, tương truyền là bản phác San Hà Xã Tắc Đồ.

Sau nhiều năm tu hành và nghiên ngẫm, ông Lâm quyết định dựng lại bức họa, từng đoạn từng nét. Bức tranh cần được vẽ lên một tấm lụa dài \(n\) thước, chia làm \(n\) đoạn liên tiếp, mỗi đoạn ứng với một phần của thế giới trong tranh. Ông đã xác định được mức màu sắc thích hợp cho từng đoạn, được lưu dưới dạng dãy chuỗi dài \(n\) số, mỗi số cho biết độ sáng, tối tương ứng được sử dụng.

Ban đầu, toàn bộ tấm lụa trắng trơn. Mỗi lần hành pháp (tức là vẽ), ông có thể tô một đoạn liên tiếp trên lụa bằng một màu duy nhất, nhưng ông không được tô màu sáng hơn lên màu tối hơn, vì điều đó sẽ khiến thiên địa trong tranh lộn ngược, âm dương đảo lộn. Chỉ có thể tô màu tối hơn chỗ chưa vẽ, hoặc lên màu sáng hơn.

Tuy nhiên, do thiên mệnh hữu hạn, Lâm không thể hoàn thành toàn bộ bức họa trong một lần. Vì thế, ông đang cân nhắc bỏ trống một số đoạn nhất định, không vẽ vào đó nữa -- để sau này hậu nhân hoàn thiện. Hiện tại có \(q\) kịch bản khác nhau, mỗi kịch bản cho biết một đoạn liên tiếp từ \(l\) đến \(r\) trên tấm lụa sẽ được vẽ.

Yêu cầu: Với mỗi kịch bản như vậy, hãy giúp ông Lâm tính xem: số lần hành pháp (vẽ) ít nhất cần thiết để hoàn thành bức họa, đúng theo màu sắc đã định, và không vi phạm quy tắc sáng tối.

Input

• Dòng đầu tiên gồm hai số nguyên \(n, q\) (\(n, q \leq 10^5\)) là số đoạn của tấm lụa và số kịch bản.
• Dòng thứ hai là \(n\) số \(a_1, a_2, \dots, a_n\) (\(0 \leq a_i \leq 10^9\)) biểu thị độ sáng tối của từng đoạn.
• \(q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(l\) và \(r\) (\(1 \leq l \leq r \leq n\)) cho biết đoạn sẽ vẽ.

Output

• Với mỗi kịch bản, in ra một dòng chứa số nguyên là số lần vẽ tối thiểu cần thiết để hoàn thành bức họa.

Example

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

2
4
4
3
5

Scoring

• \(30\%\) số điểm thỏa mãn \(n, q \leq 100\)
• \(20\%\) số điểm khác với \(n, q \leq 1000\)
• Còn lại không có điều kiện gì thêm