Имеется массив натуральных чисел a
1, a
2, ..., a
n. Рассмотрим некоторый его подмассив a
l, a
l + 1, ..., a
r, где 1 ≤ l ≤ r ≤ n, и для каждого натурального числа s обозначим через K
s число вхождений числа s в этот подмассив. Назовем мощностью подмассива сумму произведений K
s·K
s·s по всем различным натуральным s. Так как количество различных чисел в массиве конечно, сумма содержит лишь конечное число ненулевых слагаемых.
Необходимо вычислить мощности каждого из t заданных подмассивов.
Входные данные
Первая строка содержит два целых числа n и t (1 ≤ n, t ≤ 200000) — длина массива и количество запросов соответственно.
Вторая строка содержит n натуральных чисел ai (1 ≤ a
i ≤ 10
6) — элементы массива.
Следующие 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
2 7
1 6
2 7 |
20
20
20 |