Cho dãy số nguyên gồm n phần tử a₁,a₂,...,a_n. Định nghĩa dãy con của một dãy số là dãy mới được tạo sau khi bỏ đi một vài phần tử của dãy ban đầu (hoặc không bỏ phần tử nào). Ví dụ dãy [3,2,5] là dãy con của dãy [3,5,2,9,5]. Dãy rỗng (không gồm phần tử nào) là dãy con của mọi dãy số, dãy rỗng thì có tổng là 0.

Yêu cầu: Gồm Q truy vấn, mỗi truy vấn gồm một cặp số (L,R) (1 ≤ L ≤ R ≤ n). Với mỗi truy vấn, bạn hãy tìm dãy con của dãy [a_L,a_L+1,...,a_R] có tổng lớn nhất, in ra tổng đó.

Dữ liệu: 

+ Dòng đầu chứa hai số nguyên n và Q (n, Q ≤ 10⁵);

+ Dòng thứ hai chứa n số nguyên a₁,a₂,...,a_n (|a_i| ≤ 10⁵; i = 1, 2, …, n);

+ Q dòng sau, mỗi dòng là một cặp số nguyên dương (L,R) (1 ≤ L ≤ R ≤ n).

Kết quả: 

Gồm Q dòng, mỗi dòng là kết quả bài toán ứng với cặp (L,R).

Ví dụ: