Powerful array

题意翻译

- 给定长度为 $n$ 的序列 $a$,有 $q$ 次询问,每次询问给出两个数 $l,r$。 - 对于每次询问,设 $cnt_i$ 表示 $i$ 在 $a_l,a_{l+1},\cdots,a_r$ 出现的次数,您需要求出 $\displaystyle\sum_i cnt_i^2\cdot i$。 - $1\le n,q\le 2\times 10^5$,$1\le a_i\le 10^6$,$1\le l\le r\le n$。

题目描述

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

输入输出样例

输入样例 #1

3 2
1 2 1
1 2
1 3

输出样例 #1

3
6

输入样例 #2

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

输出样例 #2

20
20
20

说明

Consider the following array (see the second sample) and its \[2, 7\] subarray (elements of the subarray are colored): ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF86D/5e3c36b108711f9f95c3c3519472e9f583328f8b.png) 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 $ .