C. Тенцинг и шарики
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод
Enjoy erasing Tenzing, identified as Accepted!

У Тенцинга есть $$$n$$$ шариков, расположенных в один ряд. Цвет $$$i$$$-го шарика слева — $$$a_i$$$.

Тенцинг может проделать следующую операцию любое количество раз:

  • выбрать $$$i$$$ и $$$j$$$ такие, что $$$1\leq i < j \leq |a|$$$ и $$$a_i=a_j$$$,
  • удалить из массива $$$a_i,a_{i+1},\ldots,a_j$$$ (и уменьшить индексы всех элементов справа от $$$a_j$$$ на $$$j-i+1$$$).

Тенцинг хочет узнать максимальное количество шариков, которое он может удалить.

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

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

Первая строка содержит одно целое число $$$n$$$ ($$$1\leq n\leq 2\cdot 10^5$$$) — количество шариков.

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

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

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

Для каждого набора входных данных выведите максимальное количество шариков, которые может удалить Тенцинг.

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

В первом примере Тенцинг выберет $$$i=2$$$ и $$$j=3$$$ в первой операции так, что $$$a=[1,3,3]$$$. Затем Тенцинг снова выберет $$$i=2$$$ и $$$j=3$$$ во второй операции так, что $$$a=[1]$$$. Таким образом, Тенцинг может удалить в общей сложности $$$4$$$ шарика.

Во втором примере Тенцинг выберет $$$i=1$$$ и $$$j=3$$$ в первой и единственной операции так, что $$$a=[2]$$$. Таким образом, Тенцинг может удалить $$$3$$$ шарика.