SP1043 GSS1 - Can you answer these queries I

给定一个长度为 $N$ 的序列 $A_1,A_2, \dots ,A_N (|A_i| \le 15007,1 \le N \le 50000)$。查询定义如下： $$ Query(x,y) = \max{\{A_i+A_{i+1}+ \dots +A_j}\},x \le i \le j \le y $$ 给出 $M$ 个查询，你的程序必须输出这些查询的结果。

第 $1$ 行包含一个正整数 $N$； 第 $2$ 行包含 $N$ 个整数，表示序列 $A$ 中的数； 第 $3$ 行包含一个正整数 $M$； 接下来 $M$ 行，第 $i$ 行包含两个整数 $x_i$ 和 $y_i$。

输出 $M$ 个查询的结果，每个查询结果占一行。

对于 $100\%$ 的数据，$|A_i| \le 15007,1 \le N \le 50000$。