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