Background

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

Description

.

Format

Input

第一行，为一个正整数 n。

第二行，为 n个正整数 a1,a2,⋯ ,an

第三行，为一个正整数 。

接下来 m 行，每行为两个正整数 li,ri ，满足 1≤li​≤ri​≤n.

Output

共 m** 行。

第 i 行为第 i 组答案的询问

Samples

4
4 3 2 1
2
1 4
2 3

10
5

区间1到4的和是10，所以第一行输出10

# Limitation

1s, 1024KiB for each test case.