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

Description

给出一个数列（元素个数不超过 20000），数列元素均为三位数以内的负整数、正整数、0。求这个数列中一段子序列的和。

共有 M 次询问，每次询问都会给出这个子序列的左右两端的位置，请你求出这一段子序列的和。

Format

Input

第一行仅一个整数 N（1 ≤ N ≤ 20000）；

第二行有 N 个整数。

第三有仅有一个整数 M（1 ≤ M ≤ 20000）；

接下来有 M 行，每行有两个整数 a，b。 .

Output

输出有 M 行，每行表示一个询问的子序列的和。

Samples

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

-1
0