### 问题描述 现有 $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$。 ### 输出格式 对于每组查询，输出该区间最大连续子序列的和。 ### 样例输入 ```text 8 1 4 -3 8 -9 2 -2 1 4 1 5 2 8 3 6 3 3 ``` ### 样例输出 ```text 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$。