M. Пары равных

Дан массив. На каждый запрос $(l, r)$ нужно сказать, сколько пар индексов $i < j$ внутри отрезка дают $a_i = a_j$.

Если значение $v$ встречается на отрезке $c_v$ раз, оно даёт $\binom{c_v}{2}$ пар. Ответ - сумма по всем значениям. Пересчитывать сумму целиком на каждый шаг нельзя, но её можно поддерживать разностно.

В первой строке - число $n$ ($1 \le n \le 10^5$).

Во второй строке - $n$ чисел $a_i$ ($1 \le a_i \le 10^6$).

В третьей строке - число запросов $q$ ($1 \le q \le 10^5$).

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

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