当前没有测试数据。

题目描述

You are given a sequence $a_1, a_2, ..., a_N$ . ( $|a_i| ≤ 15007$ , $1 ≤ N ≤ 50000$ ). A query is defined as follows: $Query(x,y) = Max\{a_i+a_{i+1}+...+a_j;x≤i≤j≤y\}$. Given M queries, your program must output the results of these queries.

输入格式

The first line of the input file contains the integer N. In the second line, N numbers follow. The third line contains the integer M. M lines follow, where line i contains 2 numbers xi and yi.

输出格式

Your program should output the results of the M queries, one query per line.

测试样例

3 
-1 2 3
1
1 2

2