C. Нуль-сортировка
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод
An array is sorted if it has no inversions
A Young Boy

Вам дан массив из $$$n$$$ целых положительных чисел $$$a_1,a_2,\ldots,a_n$$$.

За одну операцию вы можете выполнить следующие действия:

  1. Выбрать любое число $$$x$$$.
  2. Для всех $$$i$$$ таких, что $$$a_i = x$$$, выполнить $$$a_i := 0$$$ (присвоить $$$0$$$ значению $$$a_i$$$).

Найдите минимальное количество операций, необходимых для того, что отсортировать массив в неубывающем порядке.

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

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

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

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

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

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

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

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

В первом наборе входных данных вы можете выбрать $$$x = 3$$$ при применении операции, тогда итоговый массив будет равен $$$[0, 0, 2]$$$.

Во втором наборе входных данных, вы можете выбрать $$$x = 1$$$ при применении первой операции и $$$x = 3$$$ при применении второй операции, тогда итоговый массив будет равен $$$[0, 0, 0, 0]$$$.