题目描述

给定一个长度为 $n$ 的数组 $a$，再进行 $q$ 次询问，每次询问输入一个 $l, r$，对于每次询问，请你输出 $a_l \sim a_r$ 的总和。

提示：本题为超纲题，若想完成，请看最后的提示。

输入格式

第一行一个正整数 $n$。

第二行输入 $n$ 个正整数 $a_i$。

第三行输入一个正整数 $q$。

接下来 $q$ 行，每行输入两个正整数 $l,r$。

输出格式

对于每次询问，分行输出 $a_l \sim a_r$ 的和。

5
1 3 7 4 5
2
2 4
1 3

14
11

数据规模与约定

对于 $100\%$ 的数据，$1 \le n,q \le 10^5, 1 \le a_i \le 100, 1 \le l \le r \le n$。

提示

本题暴力算肯定是超时的。

下面说的你可以在草稿纸上模拟一下，假设你求出来一个数组 $s$，$s[i]$ 表示 $a[1] + a[2] + \dots + a[i]$ 的总和。

那么，你可以思考一下，如果要求 $a[l]+ \dots +a[r]$，能否利用上 $s$ 数组来快速求区间和呢？

另外，如何用比较快的方式求出 $s$ 数组呢？