区间加权和

题目描述

输入一个长度为 $n$ 的整数序列 $a$，下标从 $1$ 开始。

接下来再输入 $m$ 个询问，每个询问输入一对 $l,r$。

记每次询问的连续子序列 $[a_l, a_{l+1}, ..., a_r]$ 为序列 $A$: $[A_1, A_2, ..., A_{r-l+1}]$.

对于每个询问，求 $\sum_{i=1}^{|A|} (A_i * i)$ 的值。

输入描述

第一行包含两个整数 $n$ 和 $m$。

第二行包含 $n$ 个整数，表示整数数列。

接下来 $m$ 行，每行包含两个整数 $l$ 和 $r$，表示一个询问的区间范围。

输出描述

共 $m$ 行，每行输出一个询问的结果。

样例输入

5 3
2 1 3 6 4
1 2
1 3
2 4

样例输出

4
13
25

样例解释

对于第一组询问，结果为 $2 * 1 + 1 * 2 = 4$；

对于第二组询问，结果为 $2 * 1 + 1 * 2 + 3 * 3 = 13$；

对于第三组询问，结果为 $1 * 1 + 3 * 2 + 6 *3 = 25$。

数据范围与约定

对于 $50\%$ 的数据，$1 \le n,m \le 5000$；

对于 $100\%$ 的数据，$1 \le n,m \le 10^5$，$1 \le l \le r \le n$，序列中的每个值 $x$ 满足 $x \in [-10^6, 10^6]$.