该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

徐老师最近在玩一款 $RPG$ 游戏，游戏内一共有 $n$ 个房间，依次排列成一排，编号分别为 $1 \sim n$

其中有的房间内存在 陷阱，进入会扣血，有的房间内有 恢复药水，进入能够回复血量

每一轮游戏会随机设定一段连续的房间 $[l,r]$，游戏要求玩家从 $l$ 号房间出发依次经过 $l+1,l+2,\dots$ 到达 $r$ 号房间

但是徐老师最近玩这个游戏很上头，于是他给自己制作了一款外挂！

徐老师可以在每一轮游戏规定的房间内任意传送，而不用遵循按顺序经过房间的要求，也可以在任意时刻结束这轮游戏（可以不进入任何房间）

并且徐老师发现有 恢复药水 的房间，只有第一次进入才能回复血量，第二次开始就没有效果了。

现在徐老师想知道，每一轮他最多可以得到多少点血量加成？（这里我们认为徐老师的血量没有上限）

输入格式

输入第一行包含一个整数 $n$ 表示房间数量

输入第二行包含 $n$ 个整数 $a_i$

如果 $a_i < 0$ 则表示第 $i$ 个房间内是 陷阱，进入会扣除 $|a_i|$ 点血量

如果 $a_i = 0$ 则表示第 $i$ 个房间内什么都没有，血量不会发生变化

如果 $a_i > 0$ 则表示第 $i$ 个房间内是 恢复药水，第一次进入会回复 $a_i$ 点血量

输入第三行包含一个整数 $T$ 表示有 $T$ 轮游戏

接下来 $T$ 行，每行两个整数 $l_i,r_i$ 表示这一轮游戏选取的房间编号

输出格式

对于每一轮游戏，输出这轮游戏中徐老师最多能回复的血量值

数据范围

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

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

样例输入

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

样例输出

6
13
9
13