Олимпиадный тренинг

Задача . Мощный массив


Имеется массив натуральных чисел a1, a2, ..., an. Рассмотрим некоторый его подмассив al, al + 1, ..., ar, где 1 ≤ l ≤ r ≤ n, и для каждого натурального числа s обозначим через Ks число вхождений числа 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
2 7
1 6
2 7
20
20
20

time 5000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w647
Комментарий учителя