C. Парный вес последовательности
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вес последовательности определяется как количество пар $$$(i,j)$$$ (здесь $$$i \lt j$$$) с равными значениями ($$$a_{i} = a_{j}$$$). Например, вес последовательности $$$a = [1, 1, 2, 2, 1]$$$ равен $$$4$$$. Множество неупорядоченных пар индексов с равными значениями: $$$(1, 2)$$$, $$$(1, 5)$$$, $$$(2, 5)$$$, и $$$(3, 4)$$$.

Вам задана последовательность $$$a$$$ из $$$n$$$ чисел. Найдите сумму весов всех подотрезков $$$a$$$.

Последовательность $$$a$$$ является подотрезком $$$b$$$, если $$$a$$$ может быть получена из $$$b$$$ удалением нескольких (возможно, ни одного или всех) элементов из начала и нескольких (возможно, ни одного или всех) элементов из конца.

Входные данные

Первая строка содержит целое число $$$t$$$ ($$$1 \le t \le 10^5$$$) — количество наборов входных данных. Далее идет описание наборов.

Первая строка каждого набора входных данных содержит целое число $$$n$$$ ($$$1 \le n \le 10^5$$$).

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$).

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$10^5$$$.

Выходные данные

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

Пример
Входные данные
2
4
1 2 1 1
4
1 2 3 4
Выходные данные
6
0
Примечание
  • В примере $$$1$$$, все возможные подотрезки $$$[1, 2, 1, 1]$$$ имеющие размер более $$$1$$$ это:
    1. $$$[1, 2]$$$ содержит $$$0$$$ пар;
    2. $$$[2, 1]$$$ содержит $$$0$$$ пар;
    3. $$$[1, 1]$$$ содержит $$$1$$$ пару;
    4. $$$[1, 2, 1]$$$ содержит $$$1$$$ пару;
    5. $$$[2, 1, 1]$$$ содержит $$$1$$$ пару;
    6. $$$[1, 2, 1, 1]$$$ содержит $$$3$$$ пары.
    Таким образом ответ $$$6$$$.
  • В примере $$$2$$$ все элементы различны. Таким образом, ни для одного подотрезка нет подходящей пары. Ответ $$$0$$$.