D. Мощность подсписка

У каждого из $n$ юнг известен рост. Для подсписка $a_l, \ldots, a_r$ обозначим через $K_s$ число юнг ростом ровно $s$ в этом подсписке. Мощностью подсписка назовём

где сумма берётся по всем встречающимся значениям роста. Нужно посчитать мощность каждого из $t$ заданных подсписков.

В первой строке $n$ и $t$ ($1 \le n, t \le 10^5$) — длина списка и количество запросов. Во второй строке $n$ натуральных чисел $a_i$ ($1 \le a_i \le 10^5$) — рост юнг.

В следующих $t$ строках по два числа $l$ и $r$ ($1 \le l \le r \le n$).

Выведите $t$ строк — мощности подсписков в порядке запросов.