题目描述

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

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

输入格式：

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

第二行有 N 个整数。

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

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

输出格式：

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

输入样例1：

5

4 -5 3 2 4

2

1 2

2 4

输出样例1：

-1

0