Phong là một học sinh rất say mê các hoạt động STEM và rất thích thực hiện những thí nghiệm thực tế. Trong một lần thí nghiệm, Phong đã đo nhiệt độ trung bình trong \(n\) ngày liên tiếp và được các kết quả là các số nguyên đôi một khác nhau.

Tiếp theo, Phong thực hiện các bước tách nhóm dữ liệu. Với mỗi bước, Phong sẽ tìm ngày có nhiệt độ cao nhất và ngày có nhiệt độ thấp nhất trong dãy, sau đó tách dữ liệu nhiệt độ của các ngày nằm trong đoạn giữa hai ngày này (kể cả hai ngày có nhiệt độ cao nhất và thấp nhất) thành một nhóm, và nối dữ liệu của các ngày còn lại thành một dãy mới (giữ nguyên thứ tự). Phong lặp lại quy trình này trên dãy mới cho đến khi dãy này trở thành dãy rỗng và đếm số nhóm đã tách được.

Phong thực hiện quy trình tách nhóm dữ liệu này với \(q\) bộ dữ liệu khác nhau, mỗi bộ dữ liệu là nhiệt độ trung bình của các ngày trong một đoạn liên tiếp từ ngày thứ \(l\) đến ngày thứ \(r\). Vì dữ liệu gồm rất nhiều ngày nên việc tính toán bằng tay có thể mất rất nhiều thời gian, Phong muốn nhờ bạn viết một chương trình tính nhanh số nhóm mà Phong tách được. Bạn hãy giúp Phong tính toán thông tin này nhé.

Input

• Dòng đầu tiên gồm hai số nguyên dương \(n, q\) (\(1 \le n \le 2 \cdot 10^5, 1 \le q \le 500\)).
• Dòng tiếp theo gồm \(n\) số nguyên dương \(a_1, a_2, \ldots, a_n\) (\(1 \le a_i \le 2 \cdot 10^5\)), các giá trị \(a_i\) đôi một khác nhau.
• \(q\) dòng tiếp theo, mỗi dòng gồm hai số nguyên dương \(l, r\) (\(1 \le l \le r \le n\)).

Output

• Với mỗi bộ dữ liệu, in ra số nhóm mà Phong tách được.

Example

7 3
5 2 8 1 9 3 7
1 7
2 6
1 3

4
3
2

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(n = 2000, q = 1\).
• Subtask \(2\) (\(30\%\) số điểm): \(q = 1\), không có ràng buộc gì thêm về \(n\).
• Subtask \(3\) (\(20\%\) số điểm): Không có ràng buộc gì thêm.