Problem1336--！（简单）的线段树

1336: ！（简单）的线段树

Time Limit: 4 Sec  Memory Limit: 128 MB
Submit: 12  Solved: 1
[Status] [Submit] [Creator:]

Description

给你一个序列A[1],A[2],...,A[n].（|A[i]| <= 15007, 1 <= N <= 50,000）.
M(1 <= M <= 500,000) 次询问，每次询问 Query(x, y) = Max{A[i] + A[i+1] +...+ A[j]; x <= i <= j <= y}.

Input

第一行输入一个数N。
第二行输入N个数A[1],A[2],...,A[n].
第三行输入一个数M
以下M行，每行输入x , y.

Output

M行，每行输出查询的答案。

Sample Input Copy 

3
-1 2 3
1
1 2

Sample Output Copy 

2

Source/Category

 
[Submit] [Status]