Description

ymf收到反馈， 说1544. 求和查询 太过简单， 为了响应萌新 ， 这不 出了个升级版。

Format

Input

第一行给出一个n（1 <= n <= 100000）， 代表有n个数

接下来一行中有n个数a[i]， 下标从1 开始 (1 <= a[i] <= 10000)

接下来给出一个q (0 <= q <= 100000)

表示接下来有 q 行， 每行两个数 l(1 <= l <= 10000), r (l <= r <= 100000)

Output

一共q行， 每行一个数， 表示从 a[l] + ... + a[r] ， (即从下标l， 加到下标r 的和)

Samples

3
1 2 3
2
1 2
1 3

3
6

Hints

请各位注意时限哦~
做不出来的可以搜一下前缀和这个东西呀， 这是数组的基本应用之一~