Problem
有一个自然数数组 a
1, a
2, ..., a
n。考虑它的一些子数组 a
l, a
l + 1, ..., a
r,其中 1 ≤ l ≤ r ≤ n，对于每个自然数 s，用 K
s 表示数字 s 在该子数组中出现的次数。我们称子数组的基数为 Ks·Ks·s 在所有不同整数 s 上的乘积之和。由于数组中不同数字的数量是有限的，因此总和仅包含有限数量的非零项。
需要计算给定的 t 个子数组中的每一个的基数。
输入
第一行包含两个整数 n 和 t (1 ≤ n, t ≤ 200000) —分别是数组的长度和请求的数量。
第二行包含n个自然数ai (1 ≤ ai ≤ 106) —数组元素。
接下来的 t 行包含两个正整数 l 和 r (1 ≤ l ≤ r ≤ n) —对应子数组左右两端的索引。
印记
打印 t 行，其中第 i 行包含唯一的自然数——第 i 个查询子数组的基数。
示例：
<正文>
| 输入 |
输出 |
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 |