Имеется массив натуральных чисел 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-го запроса.
Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-х битовых чисел на С++. Рекомендуется использовать поток cout (также вы можете использовать спецификатор %I64d).
Рассмотрим следующий массив (см. пример 2) и его подмассив [2, 7] (цветом выделены элементы подмассива):
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
5000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач