F. Ты так красива
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дан массив целых чисел $$$a_1, a_2, \ldots, a_n$$$. Посчитайте количество подотрезков этого массива $$$1 \leq l \leq r \leq n$$$, таких что:

  • Массив $$$b = [a_l, a_{l+1}, \ldots, a_r]$$$ встречается в массиве $$$a$$$ как подпоследовательность ровно один раз. Другими словами, существует ровно один способ выбрать набор индексов $$$1 \leq i_1 < i_2 < \ldots < i_{r - l + 1} \leq n$$$, такой что $$$b_j = a_{i_j}$$$ для всех $$$1 \leq j \leq r - l + 1$$$.
Входные данные

Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит единственное целое число $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — количество наборов входных данных. Далее следует их описание.

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

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

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

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

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

Пример
Входные данные
6
1
1
2
1 1
3
1 2 1
4
2 3 2 1
5
4 5 4 5 4
10
1 7 7 2 3 4 3 2 1 100
Выходные данные
1
1
4
7
4
28
Примечание

В первом наборе входных данных существует ровно один подотрезок $$$(1, 1)$$$, который нам подходит.

В втором наборе входных данных существует ровно один подотрезок $$$(1, 2)$$$, который нам подходит. Подотрезки $$$(1, 1)$$$ и $$$(2, 2)$$$ нам не подходят, так как подпоследовательность $$$[1]$$$ встречается два раза в массиве.

В третьем наборе входных данных подходят все подотрезки кроме $$$(1, 1)$$$ и $$$(3, 3)$$$.