M. Тройки равных

То же, что классная задача M, только считать надо не пары, а тройки индексов $i < j < k$ с $a_i = a_j = a_k$.

В первой строке - число $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$).

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