Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×

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

Задан целочисленный массив $$$a$$$ размера $$$n$$$. Подмассивом массива $$$a$$$ назовем его непрерывную подпоследовательность (то есть массив $$$[a_l, a_{l+1}, \dots, a_r]$$$ для некоторых $$$l$$$ и $$$r$$$, удовлетворяющих условию $$$1 \le l < r \le n$$$). Назовем подмассив уникальным, если в нем есть целое число, которое встречается ровно один раз.

Вы можете выполнять следующую операцию любое количество раз (возможно, ни разу): выберите элемент массива и замените его любым целым числом.

Ваша задача — посчитать минимальное количество вышеописанных операций, чтобы все подмассивы массива $$$a$$$ стали уникальными.

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

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

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

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

Дополнительное ограничение на входные данные: сумма $$$n$$$ по всем наборам входных данных не превышает $$$3 \cdot 10^5$$$.

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

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

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

Во втором наборе входных данных можно заменить $$$1$$$-й и $$$3$$$-й элемент, например, следующим образом: $$$[3, 4, 1, 4]$$$.

В третьем наборе входных данных можно заменить $$$4$$$-й элемент, например, следующим образом: $$$[3, 1, 2, 3, 2]$$$.