Sương mây mịt mùng

Núi sông điệp trùng

Chân không chịu dừng

Leo, leo đèo

Vào ngày cuối cùng của kì nghỉ hè, 4 cô gái đến từ Shimokitazawa quyết định đi chơi có thêm thật nhiều kỉ niệm đẹp. Họ ghé thăm những quán ăn, bờ biển, và cuối cùng đặt chân đến một đài quan sát cao chót vót, buộc họ phải leo thang lên từ mặt đất. Kita - người hướng ngoại nhất nhóm - rất muốn cả nhóm cùng leo lên những bậc thang đó, nhưng ba người còn lại là Bocchi, Ryo và Nijika cảm thấy quá mệt mỏi và tìm cách khác để tận hưởng việc leo thang. May thay, họ có thể sử dụng thang cuốn ở gần đó để thay thế. Trên đường lên thang cuốn, Bocchi bỗng nhận thấy những tính chất rất đặc biệt của những bậc thang trước mắt, chúng có hình thù giống như những ngọn đồi trùng điệp. Từ quan sát thú vị đó, Bocchi nảy ra bài toán sau:

Bocchi giả sử độ cao của những bậc thang cô thấy là một mảng ~N~ phần tử ~a_1, a_2, \dots, a_N \ (-10^9 \leq a_i \leq 10^9)~ (thường xuyên sống trong bóng tối khiến Bocchi tưởng tượng bậc thang có độ cao âm). Bocchi gọi một dãy ~l, r~, với ~1 \leq l \leq r \leq N~ là dãy "đồi núi" nếu ~a_l = a_r~ và với mọi ~l \leq i \leq r~, ta có ~a_l \geq a_i~. Điều này cũng đồng nghĩa dãy ~l = r~ cũng là một dãy "đồi núi". Bocchi quy ước độ đẹp của một dãy "đồi núi" là ~r - l~.

Do đang di chuyển trên thang cuốn, mỗi lần quan sát của Bocchi không cố định. Cụ thể, Bocchi có tổng cộng ~Q~ lần quan sát. Ở lần thứ ~i~, cô nhìn thấy các số trong khoảng ~[L_i, R_i] \ (1 \leq L_i \leq R_i \leq N)~. Trong mỗi lần quan sát, Bocchi muốn biết độ dài của dãy "đồi núi" dài nhất nằm trong tầm nhìn của cô. Nói cách khác, với mỗi ~[L_i, R_i]~, Bocchi muốn tìm dãy "đồi núi" ~[x, y]~ có độ đẹp lớn nhất thỏa mãn ~L_i \leq x \leq y \leq R_i~. Dễ thấy luôn tồn tại đáp án thỏa mãn.

Do mắc chứng sợ giao tiếp xã hội nặng, Bocchi có thể bất chợt nổ tung hoặc tan chảy nếu bị buộc phải giao tiếp với người khác. Nên cô đã chuyển lời cho Nijika, và giờ là bạn. Hãy giúp Bocchi nhé!

Input

• Dòng đầu chứa hai số nguyên dương ~N, Q \ (1 \leq N, Q \leq 2 \times 10^5)~.
• Dòng thứ hai chứa ~N~ số nguyên ~a_1, a_2, \dots, a_N \ (-10^9 \leq a_i \leq 10^9)~ được ngăn bởi dấu cách.
• Q dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên dương ~L_i, R_i \ (1 \leq L_i \leq R_i \leq N)~ biểu thị lần quan sát thứ ~i~ của Bocchi.

Output

• In ra ~Q~ dòng, với dòng thứ ~i~ là kết quả cho lần quan sát thứ ~i~ của Bocchi.

Scoring

• Subtask 1 ~(14p)~: ~N, Q \leq 300~.
• Subtask 2 ~(17p)~: ~N \leq 5000~.
• Subtask 3 ~(13p)~: ~L_i = 1~ với mọi ~1 \leq i \leq Q~.
• Subtask 4 ~(15p)~: ~L_1 \leq R_1 < L_2 \leq R_2 < L_3 \leq ... \leq R_{Q - 1} < L_Q \leq R_Q~.
• Subtask 5 ~(17p)~: ~a_i \in \{0, 1\}~ với mọi ~1 \leq i \leq N~.
• Subtask 6 ~(24p)~: Không có ràng buộc gì thêm.

Sample Input 1

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

Sample Output 1

1
2
2
2
0
1
0
2
0
0

Notes

• Ở lần quan sát đầu tiên, Bocchi có thể chọn đoạn ~[4, 5]~.
• Ở lần quan sát thứ hai, Bocchi có thể chọn đoạn ~[3, 5]~.

Sample Input 2

5 5
1 -2 1 -2 1
1 3
2 4
3 5
5 5
1 5

Sample Output 2

2
0
2
0
4

Notes

• Các đoạn có thể chọn trong các truy vấn là ~(1, 3), (2, 2), (3, 5), (5, 5), (1, 5)~.