Cho một dãy A gồm n số nguyên ~a_1, a_2,..., a_n~. Đoạn con ~a_i ,a_{i +1}, ..., a_j~ (1 ≤ i ≤ j ≤ n) được gọi là đoạn con liên tiếp từ phần tử thứ i đến phần tử thứ j của dãy A, có độ dài là j - i + 1 và tổng là ~a_i + a_{i+1} + ... +a_j~

Yêu cầu: Hãy tìm tổng lớn nhất của đoạn con liên tiếp có độ dài từ p đến q.

Dữ liệu: Vào từ file văn bản SUBM.INP có cấu trúc:

• Dòng đầu tiên chứa số nguyên dương n (n ≤ ~10^6~);

• Dòng thứ 2 chứa 2 số nguyên p, q (1 ≤ p ≤ q ≤ n);

• Dòng thứ 3 chứa n số nguyên ~a_1, a_2,..., a_n~ (~|a_i| ≤ 10^9~, 1 ≤ i ≤ n). Các số trên cùng một dòng ghi cách nhau một dấu cách.

Kết quả: Ghi ra file văn bản SUBM.OUT một số nguyên duy nhất là tổng lớn nhất tìm được.

Ràng buộc:

• Có 40% số test của bài thỏa mãn điều kiện: ~n ≤ 10^3~.
• 30% số test của bài thỏa mãn điều kiện: ~n ≤ 10^6~ và ~p = q~.
• Có 30% số test của bài thỏa mãn điều kiện: ~n ≤ 10^6~.

Ví dụ:

SUBM.INP

5
2 3
3 -2 5 -1 6

SUBM.OUT

10  

Giải thích

• Các đoạn con liên tiếp có độ dài bằng 2:
  • 3, -2 có tổng bằng 1,
  • -2, 5 có tổng bằng 3,
  • 5, -1 có tổng bằng 4,
  • -1, 6 có tổng bằng 5.
• Các đoạn con liên tiếp có độ dài bằng 3:
  • 3, -2, 5 có tổng bằng 6,
  • -2, 5, -1 có tổng bằng 2,
  • 5, -1, 6 có tổng bằng 10 (lớn nhất)

Bài 2:

Tải về

Bài 3:

Tải về

Bài 4:

Tải về