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
2015-09-01 18:11:30 Phạm Ngọc Hiếu
cùng 1 code, lúc thì tle lúc thì ac >_<
2015-08-25 19:04:57 N�ng D�n John
Đúng, nhiều lúc muốn đấm vào mặt mình thiệt :(((((((
2014-12-13 15:06:58 Sue
nhiều lúc muốn tự đấm vào mặt sao tối ưu nó rồi mà vẫn TLE :v
2014-10-24 11:47:39 [ND]๖ۣۜMiniString
bài này cho bớt 1 số 0 đi được ko
2013-07-26 03:10:20 a;slkfjasl;fkj
chuối ơi là chuối :(
2013-06-20 13:59:51 ๖ۣۜLove๖ۣۜ
RMQ ư ?
2013-06-01 10:36:20 [KC]★★★★ - darkmagician
mjnh xet tu a1-->a2 tim doan con tong lon nhat -> doan con gom a2->kq=2
2012-11-08 08:32:27 a;slkfjasl;fkj
sao lại ra 2 hey
2011-11-02 17:00:06 KHD
IT thôi
2011-07-19 15:09:32 pham tuan minh
bai nay dung interval tree nhung ko biet lam the nao de ac nhi
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.