Problem
There is an array of natural numbers a
1, a
2, ..., a
n. Consider some of its subarrays a
l, a
l + 1, ..., a
r, where 1 ≤ l ≤ r ≤ n, and for each natural number s denote by K
s the number of occurrences of the number s in this subarray. Let's call the cardinality of a subarray the sum of the products K
s·K
s·s over all distinct integers s. Since the number of different numbers in the array is finite, the sum contains only a finite number of non-zero terms.
It is necessary to calculate the cardinalities of each of the t given subarrays.
Input
The first line contains two integers n and t (1 ≤ n, t ≤ 200000) — the length of the array and the number of requests, respectively.
The second line contains n natural numbers ai (1 ≤ a
i ≤ 10
6) — array elements.
The next t lines contain two positive integers l and r (1 ≤ l ≤ r ≤ n) — indexes of the left and right ends of the corresponding subarray.
Imprint
Print t lines, where the i-th line contains the only natural number — cardinality of the i-th query subarray.
Examples:
| Input |
Output |
3 2
1 2 1
1 2
1 3
| 3
6 |
8 3
1 1 2 2 1 3 1 1
27
16
27 |
20
20
20 |