Coding is the closest thing we have to superpower ！
描述
给定一个序列A[1], A[2], A[3], ..., A[N]。
定义Query(x,y) = Max \{ a[i]+a[i+1]+...+a[j] ; x \le i \le j \le y \} 。
给出M个查询(x, y)，对于每一个查询，输出它们的值。
输入
第一行包含一个整数N(1 \le N \le 5 \cdot 10^4)。
第二行给出N个整数A[1], A[2], A[3], ..., A[N] (|A[i]| \le 15007)。
接下来一个整数M(1 \le M \le 5 \cdot 10^5)。
接下来M行，每行两个整数x, y(1 \le x \le y \le N)，表示一个查询。
输出
对于每一个查询，输出一个答案占一行。
样例
输入
3 -1 2 3 1 1 2
输出
2
标签