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 ai (1 ≤ ai ≤ 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.
输出描述:
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<br />1 2 1<br />1 2<br />1 3<br />8 3<br />1 1 2 2 1 3 1 1<br />2 7<br />1 6<br />2 7<br />
输出
3<br />6<br />20<br />20<br />20<br />
备注:
Consider the following array (see the second sample) and its [2, 7] subarray (elements of the subarray are colored): Then K1 = 3, K2 = 2, K3 = 1, so the power is equal to 32·1 + 22·2 + 12·3 = 20.
加载中...