Description

苹果丰收了，有n堆苹果，小红就在苹果堆旁。小红已经知道了每堆苹果有多少个。她要问一问从第a堆到第b堆一共有多少个苹果。

【数据范围】 对于%80的数据：0≤n≤10000； 对于%100的数据：0≤n≤100000。

Input

输入数字n，然后输入n个数据。 再输入问m，然后输入m行数据。

Output

输出m次a到b堆一共有多少个。

Samples

5

1 2 3 4 5

3

1 3

2 4

1 5

6

9

15

Limitation

1s, 1024KiB for each test case.