A8078. 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.

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}<=10^{6}$ ) — 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.

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).

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 $3^{2}·1+2^{2}·2+1^{2}·3=20$ .