#2619. 一段子序列和

一段子序列和

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