F. Сумма квадратов частот

Для каждого запроса $(l, r)$ нужно посчитать $\sum_v c_v^2$, где $c_v$ — сколько раз значение $v$ встречается на отрезке.

В первой строке $n$ и $q$ ($1 \le n, q \le 10^5$). Во второй строке $n$ чисел $a_i$ ($1 \le a_i \le 10^5$). В следующих $q$ строках по два числа $l$ и $r$ ($1 \le l \le r \le n$).

Для каждого запроса выведите сумму квадратов частот.