犇犇的精神粮食是一款养成类游戏，每周末都会畅玩一会。游戏内一共有 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 。