Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

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

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

Hàm q(x, y) = max { tổng(a[i]+a[i+1]+...+a[j]), x <= i <= j <= y }.

Cho m câu hỏi dạng x, y (1 <= x <= y <= n). (m <= 50000) -> hãy tính các q(x, y).

Input

- Dòng đầu là n.

- Dòng thứ hai 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

Input:
3
-1 2 3
1
1 2
Output:
2

Được gửi lên bởi:Nguyen Dinh Tu
Ngày:2006-10-24
Thời gian chạy:0.100s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:Bai` nay Hieu add day nhe ^^

hide comments
2017-08-22 20:17:09 Ðặng Minh Tiến
https://kienthuc24h.com/gss-spoj-doan-con-co-tong-lon-nhat/
2016-12-18 04:36:23
sau 1 thời trẩu thì đã ac mất logn đấm thôi
2016-10-07 09:12:05
Trâu cx AC
2016-08-18 16:17:03 Sơn Tùng M-TP
Cũng không khó lắm! Sub khoảng chục lần thôi :3
2016-05-01 07:07:00
1 tát AC, hơi sốc :)))
2016-04-15 14:20:20
xin thua, vd là 2 em đọc thành 3, làm thấy mẹ luôn cry :v
2016-02-19 04:37:14 Nguyễn Thành Nhân
duyệt trâu + nhánh cận
2015-10-14 09:39:06
THAM KHẢO TẠI https://traitaodo.wordpress.com/2015/10/14/doan-con-co-tong-lon-nhat-gss/
2015-09-08 14:12:44
https://thewizard6296.wordpress.com/2015/09/04/5/
2015-09-01 18:11:30 Phạm Ngọc Hiếu
cùng 1 code, lúc thì tle lúc thì ac >_<
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.