markdown

D. 强大的数组

每个测试的时间限制：$5$ 秒
每个测试的内存限制：$256$ MB
输入：标准输入（stdin）
输出：标准输出（stdout）

给定一个由正整数 $a_1, a_2, \dots, a_n$ 组成的数组。考虑它的任意子数组 $a_l, a_{l+1}, \dots, a_r$，其中 $1 \le l \le r \le n$。
对于每个正整数 $s$，用 $K_s$ 表示 $s$ 在该子数组中出现的次数。我们定义该子数组的强大值为所有正整数 $s$ 的 $K_s \cdot K_s \cdot s$ 之和。由于数组中不同值的个数是有限的，因此该和式中只有有限个非零项。

你需要计算 $t$ 个给定子数组的强大值。

输入

第一行包含两个整数 $n$ 和 $t$（$1 \le n, t \le 200000$）—— 分别表示数组的长度和查询的次数。
第二行包含 $n$ 个正整数 $a_i$（$1 \le a_i \le 10^6$）—— 数组的元素。
接下来的 $t$ 行，每行包含两个正整数 $l, r$（$1 \le l \le r \le n$）—— 表示对应子数组的左右端点下标。

输出

输出 $t$ 行，第 $i$ 行应包含一个正整数 —— 第 $i$ 个查询子数组的强大值。

注意：在 C++ 中，请不要使用 %lld 说明符来读入或输出 64 位整数。建议使用 cout 流（也可以使用 %I64d）。

示例

示例 1

输入

3 2
1 2 1
1 2
1 3

输出

3
6

示例 2

输入

8 3
1 1 2 2 1 3 1 1
2 7
1 6
2 7

输出

20
20
20

注释

考虑第二个示例中的数组及其子数组 $[2, 7]$（子数组中的元素已标出颜色）：
此时 $K_1 = 3$，$K_2 = 2$，$K_3 = 1$，所以强大值为 $3^2 \cdot 1 + 2^2 \cdot 2 + 1^2 \cdot 3 = 20$。