暂无测试数据。

给出 $n$ 个数的序列，每次询问给定两个数 $[l,r]$，你需要从 $a_l\sim a_r$ 这个区间里面取任意个数（可以不取），求选取的数的和的最大值。其中不选取数的时候，和为 $0$。

例如：

n = 5
5 8 9 10 11

对于区间 $[2, 4]$ 是指：$8 \ 9 \ 10$

输入格式

第 $1$ 行一个正整数 $n$ 代表序列长度。

第 $2$ 行 $n$ 个数代表序列 $a_1, a_2, \cdots, a_n$ 。

第 $3$ 行一个正整数 $q$ 代表询问组数。

第 $4 \cdots q + 3$ 行每行两个数 $l, r$ 代表一组询问区间的端点。

输出格式

$q$ 行每行一个整数代表答案。

数据范围

对于 $30\%$ 的数据保证 $1 \leq n \leq 100, 1 \leq q \leq 1000$ 。

对于 $100\%$ 的数据保证 $1 \leq n, q\leq 10^6, 0 \leq |a_i| \leq 10^9, 1\leq l \leq r \leq n$ 。

6
2 -1 2 3 -5 2
3
1 2
1 3
2 4

2
4
5

3
-1 -1 -1
1
1 3

0