H. Сумма различных

Для каждого запроса $(l, r)$ нужно посчитать сумму различных значений на отрезке: каждое встречающееся значение прибавляется ровно один раз, сколько бы раз оно ни встретилось.

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

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