Đoạn con có tổng lớn nhất

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Tác giả:
Small
Dạng bài
Điểm: 200 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Cho dãy số a[1],a[2],...,a[n] (\(|a[i]| \leq 15000 ,n \leq 50000\)).

Hàm q(x,y)=maxtổng(\(a[i]+a[i+1]+...+a[j]\)), \(x \leq i \leq j \leq y\).

Cho \(m\) câu hỏi dạng \(x,y\) (\(1 \leq x \leq y \leq n\)). (\(m \leq 50000\)).

Hãy tính các \(q(x,y)\).

Input

  • Dòng đầu là n
  • Dòng thứ 2 là dãy \(A\)
  • Dòng thứ 3 là m.
  • \(m\) dòng tiếp theo mỗi dòng là \(1\) cặp số \(x,y\).

Output

  • Lần lượt ghi ra các \(q(x,y)\) tương ứng. Mỗi kết quả ghi trên 1 dòng.

Example

Test 1

Input 
3
-1 2 3
1
1 2
Output 
2

Bình luận