F. Стек-уничтожимые массивы
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Давайте рассмотрим следующий процесс: изначально у вас есть пустой стек и массив $$$s$$$ длины $$$l$$$. Вы пытаетесь добавлять элементы массива в стек в порядке $$$s_1, s_2, s_3, \dots s_{l}$$$. Причем если стек пустой или элемент на вершине стека не равен текущему, то вы просто добавляете текущий элемент на вершину стека. Иначе вы не добавляете элемент и более того, удаляете верхний элемент стека.

Если после данного процесса стек окажется пустым, то массив $$$s$$$ считается стек-уничтожимым.

Примеры стек-уничтожимых массивов:

  • $$$[1, 1]$$$;
  • $$$[2, 1, 1, 2]$$$;
  • $$$[1, 1, 2, 2]$$$;
  • $$$[1, 3, 3, 1, 2, 2]$$$;
  • $$$[3, 1, 3, 3, 1, 3]$$$;
  • $$$[3, 3, 3, 3, 3, 3]$$$;
  • $$$[5, 1, 2, 2, 1, 4, 4, 5]$$$;

Давайте рассмотрим изменения стека более подробно при $$$s = [5, 1, 2, 2, 1, 4, 4, 5]$$$ (элемент на вершине текста выделен жирным шрифтом).

  1. после добавления $$$s_1 = 5$$$ стек будет равен $$$[\textbf{5}]$$$;
  2. после добавления $$$s_2 = 1$$$ стек будет равен $$$[5, \textbf{1}]$$$;
  3. после добавления $$$s_3 = 2$$$ стек будет равен $$$[5, 1, \textbf{2}]$$$;
  4. после добавления $$$s_4 = 2$$$ стек будет равен $$$[5, \textbf{1}]$$$;
  5. после добавления $$$s_5 = 1$$$ стек будет равен $$$[\textbf{5}]$$$;
  6. после добавления $$$s_6 = 4$$$ стек будет равен $$$[5, \textbf{4}]$$$;
  7. после добавления $$$s_7 = 4$$$ стек будет равен $$$[\textbf{5}]$$$;
  8. после добавления $$$s_8 = 5$$$ стек станет пустым.

Вам задан массив $$$a_1, a_2, \ldots, a_n$$$. Вам нужно посчитать количество подотрезков этого массива, которые являются стек-уничтожимыми.

Обратите внимание, что вам нужно ответить на $$$q$$$ независимых запросов.

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

Первая строка содержит целое число $$$q$$$ ($$$1 \le q \le 3 \cdot 10^5$$$) — количество запросов.

Первая строка каждого запроса содержит единственное целое число $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$) — длину массива $$$a$$$.

Вторая строка каждого запроса содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$) — элементы массива.

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

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

На каждый запрос выведите одно число — количество стек-уничтожимых подотрезков массива $$$a$$$.

Пример
Входные данные
3
5
2 1 1 2 2
6
1 2 1 1 3 2
9
3 1 2 2 1 6 6 3 3
Выходные данные
4
1
8
Примечание

В первом запросе есть четыре стек-уничтожимых подотрезка: $$$a_{1 \ldots 4} = [2, 1, 1, 2], a_{2 \ldots 3} = [1, 1], a_{2 \ldots 5} = [1, 1, 2, 2], a_{4 \ldots 5} = [2, 2]$$$.

Во втором запросе только один стек-уничтожимый подотрезок  — $$$a_{3 \ldots 4}$$$.

В третьем запросе есть восемь стек-уничтожимых подотрезков: $$$a_{1 \ldots 8}, a_{2 \ldots 5}, a_{2 \ldots 7}, a_{2 \ldots 9}, a_{3 \ldots 4}, a_{6 \ldots 7}, a_{6 \ldots 9}, a_{8 \ldots 9}$$$.