CF86D Powerful array

给定一个正整数数组 $a_1, a_2, \ldots, a_n$。我们来考虑它的任意一个子数组 $a_l, a_{l+1}, \ldots, a_r$，其中 $1 \leq l \leq r \leq n$。对于每一个正整数 $s$，记 $K_s$ 为该子数组中 $s$ 出现的次数。我们定义该子数组的“幂”为对每个出现过的 $s$ 计算 $K_s \cdot K_s \cdot s$ 的和。由于数组中的不同值有限，这个和中非零项是有限的。 你需要计算给定的 $t$ 个子数组的“幂”。

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

输出 $t$ 行，第 $i$ 行输出第 $i$ 个询问所对应子数组的幂。 请不要在 C++ 中使用 %lld 读取或输出 64 位整数。推荐使用 cout 流（也可以使用 %I64d）。

考虑如下数组（见第二个样例），及其 $[2, 7]$ 的子数组（子数组的元素已用色彩标记）：  在该子数组中，$K_1 = 3$，$K_2 = 2$，$K_3 = 1$，因此幂为 $3^2 \cdot 1 + 2^2 \cdot 2 + 1^2 \cdot 3 = 20$。 由 ChatGPT 5 翻译