### 问题描述

现有 $n$ 个数形成的序列 $a_i$（$i\in[1,n]$），给你 $q$ 组查询，每次查询给定一个区间 $[l,r]$（$1\le l \le r$）。你需要查询出该区间最大连续子序列的和，并将其输出。

由于输入很多，cpp 请使用 scanf 与 printf。

输入格式

第一行输入一个正整数 $n$。

第二行输入 $n$ 个正整数 $a_i$。

第三行输入一个正整数 $q$。

接下来 $q$ 行，每行输入 $2$ 个正整数 $l,r$。

输出格式

对于每组查询，输出该区间最大连续子序列的和。

样例输入

8
1 4 -3 8 -9 2 -2 1
4
1 5
2 8
3 6
3 3

样例输出

10
9
8
-3

说明

四组查询的答案分别对应为：$\text{[1 4 -3 8],[4 -3 8],[8],[-3]}$。

评测数据规模

$1\le n \le 2\times10^3,-10^3\le a_i\le 10^3,1\le q\le 2\times10^5,1\le l\le r\le n$。