## 题目描述
给出了序列A[1]，A[2]，…，A[N]。
(a[i]≤15007，1≤N≤50000)。查询定义如下：
查询(x，y)=max{a[i]+a[i+1]+...+a[j]；x≤i≤j≤y}。
给定M个查询，程序必须输出这些查询的结果。
## 输入输出格式
### 输入格式：
- 输入文件的第一行包含整数N。
- 在第二行，N个数字跟随。
- 第三行包含整数M。
- M行跟在后面，其中第1行包含两个数字xi和yi。
### 输出格式：
- 您的程序应该输出M查询的结果，每一行一个查询。
by hgc68 @ 2018-03-01 21:35:06