Background

Special for beginners, ^_^

Description

给定由 n 个正整数组成的序列 a1,a2,⋯,an和 m 个区间 [li,ri]，分别求这 m 个区间的区间和。

Format

Input

第一行包含一个正整数 n，表示序列的长度。 第二行包含 n 个正整数 a1,a2,⋯,an。 第三行包含一个正整数 m，表示区间的数量。 接下来 m 行，每行包含两个正整数 li,ri，满足 1≤li≤ri≤n。

Output

共 m 行，其中第 i 行包含一个正整数，表示第 i 组答案的询问。

Samples

4
4 3 2 1
2
1 4
2 3

10
5

Limitation

1s, 1024KiB for each test case.