CF86D.Powerful array

An array of positive integers _a_1, _a_2, ..., a__n is given. Let us consider its arbitrary subarray a__l, a__l + 1..., a__r, where 1 ≤ l ≤ r ≤ n. For every positive integer s denote by K__s the number of occurrences of s into the subarray. We call the power of the subarray the sum of products K__s·K__s·s for every positive integer s. The sum contains only finite number of nonzero summands as the number of different values in the array is indeed finite.

You should calculate the power of t given subarrays.

给定一个正整数数组 $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$ 在该子数组中出现的次数。我们定义该子数组的**权值（power）**为对所有正整数 $s$ 求和：$K_s \cdot K_s \cdot s$，即 $\sum_s K_s^2 \cdot s$。由于数组中不同数值的个数是有限的，该和式中仅有有限项非零。

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

First line contains two integers n and t (1 ≤ n, t ≤ 200000) — the array length and the number of queries correspondingly.

Second line contains n positive integers a__i (1 ≤ a__i ≤ 106) — the elements of the array.

Next t lines contain two positive integers l, r (1 ≤ l ≤ r ≤ n) each — the indices of the left and the right ends of the corresponding subarray.

第一行包含两个整数 $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$）—— 表示对应子数组的左右端点下标。

Output t lines, the i-th line of the output should contain single positive integer — the power of the i-th query subarray.

Please, do not use %lld specificator to read or write 64-bit integers in C++. It is preferred to use cout stream (also you may use %I64d).

输出 t 行，其中第 i 行应包含一个正整数——即第 i 个查询子数组的“幂”。

请注意，在 C++ 中读写 64 位整数时，请勿使用 %lld 格式说明符；推荐使用 cout 流（也可使用 %I64d）。

Consider the following array (see the second sample) and its [2, 7] subarray (elements of the subarray are colored):

Then _K_1 = 3, _K_2 = 2, _K_3 = 1, so the power is equal to 32·1 + 22·2 + 12·3 = 20.

考虑以下数组（见第二个样例）及其 [2, 7] 子数组（子数组元素已着色）：

此时 _K_₁ = 3，_K_₂ = 2，_K_₃ = 1，因此该子数组的“能量”为 3²·1 + 2²·2 + 1²·3 = 20。