Ngày ~27/3/2025~ – ngày thứ hai của vòng tuyển chọn đội tuyển quốc gia tham dự kỳ thi Olympic Tin học Châu Á - Thái Bình Dương (APIO), sangph2612 – một học sinh đến từ một trường THPT không chuyên – đã làm hết sức mình, nỗ lực như thể cậu đang viết từng dòng code cuối cùng để debug cho tình yêu.

Cậu không đặt quá nhiều kỳ vọng, nhưng khi bảng xếp hạng xuất hiện và cậu xếp hạng $28$, trái tim cậu vẫn hơi nhói một chút. Không buồn vì bị loại – mà buồn vì...

Chiếc điện thoại yêu quý của cậu đã biến mất. Chiếc điện thoại chứa:

• Lời tỏ tình draft 17 gửi cho Khánh Băng (vẫn chưa gửi)
• Code giải mấy bài khó cậu viết lúc đang... ngồi chờ tàu
• Và cả ảnh chụp màn hình những lời Khánh Băng từng nhắn: "Code sai cũng được, miễn đừng bug trái tim em là được."

Giữa lúc tâm trạng tụt mood như RAM bị leak, Sang ngồi thừ xuống băng ghế đá sau hội trường thi, mở laptop ra (may mà không mất luôn), lật lại file đề luyện cá nhân với cái tên rất đỗi kỳ cục: sad_array_problem.pdf.

Nội dung bài toán trong file như sau:

Có một mảng số nguyên $a$ gồm $n$ phần tử. Đó là chuỗi ghi nhận trạng thái cảm xúc của Sang trong $n$ ngày – tăng, giảm, hỗn loạn – trong suốt quãng thời gian ôn luyện cho vòng tuyển chọn đội tuyển tham dự APIO.

Khi nhìn lại, Sang nhận ra có những ngày mình tưởng bình thường, hóa ra lại là lúc cảm xúc thay đổi rõ rệt. Có những đoạn tưởng như trôi qua lặng lẽ, nhưng nếu sắp xếp lại – biết đâu lại thấy được điều gì đó... sắc nét hơn.

Với $q$ đoạn ngày như thế – mỗi đoạn từ ngày $l$ đến $r$ – Sang đã thử tự do sắp xếp lại các cảm xúc trong khoảng ấy, và tự hỏi: Nếu làm vậy, tổng độ chênh lệch cảm xúc giữa các ngày trong đoạn ấy sẽ lớn nhất là bao nhiêu?

Vì Sang quá buồn để có thể code nốt bài toán trên, là một người bạn của Sang, bạn hãy giúp cậu ấy AC bài toán này nhé.

Dữ liệu vào

• Dòng đầu chứa $2$ số nguyên dương $n,\ q$ $(n, q \le 4 \times 10^{5})$.
• Dòng thứ hai chứa $n$ số nguyên không âm $a_1, a_2, \dots, a_n$ $(a_i \le 10^{9})$.
• $q$ dòng tiếp theo mỗi dòng chứa hai số nguyên dương $l,\ r$ $(1 \le l \le r \le n)$.

Kết quả ra

• Xuất ra màn hình gồm $q$ dòng, dòng thứ $i$ là kết quả của truy vấn thứ $i$.

Ràng buộc

• Subtask ~1~ (~12\%~): $n, q \le 20$.
• Subtask ~2~ (~20\%~): $n, q \le 2000$.
• Subtask ~3~ (~15\%~): $max(a_i) \le 100$.
• Subtask ~4~ (~15\%~): $n, q \le 15000$.
• Subtask ~5~ (~20\%~): $n, q \le 10^{5}$.
• Subtask ~6~ (~18\%~): Không có ràng buộc gì thêm.

Ví dụ

Dữ liệu vào

5 2
1 2 3 4 8
1 5
1 3

Kết quả ra

17
3