Truy vấn Tổng Đoạn Con Lớn Nhất II

Cho mảng $n$ số nguyên và $q$ truy vấn. Với mỗi truy vấn $(a,b)$, tính tổng lớn nhất của một đoạn con liên tiếp trong phạm vi $[a,b]$ (đoạn rỗng có tổng bằng 0).

Dữ liệu vào

• Dòng đầu: hai số nguyên $n$ và $q$.
• Dòng thứ hai: $n$ số nguyên $x_1,x_2,\dots ,x_n$.
• $q$ dòng tiếp theo: mỗi dòng chứa hai số $a$ và $b$.

Dữ liệu ra

Với mỗi truy vấn, in ra một dòng chứa tổng đoạn con lớn nhất trong $[a,b]$.

Ràng buộc

• $1\le n,q\le 2\times {10}^5$
• $-{10}^9\le x_i\le {10}^9$
• $1\le a\le b\le n$

Ví dụ