C. LIS или перевернутая LIS?
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дан массив $$$a$$$ из $$$n$$$ целых положительных чисел.

Пусть $$$\text{LIS}(a)$$$ обозначает длину самой длинной строго возрастающей подпоследовательности $$$a$$$. Например,

  • $$$\text{LIS}([2, \underline{1}, 1, \underline{3}])$$$ = $$$2$$$.
  • $$$\text{LIS}([\underline{3}, \underline{5}, \underline{10}, \underline{20}])$$$ = $$$4$$$.
  • $$$\text{LIS}([3, \underline{1}, \underline{2}, \underline{4}])$$$ = $$$3$$$.

Мы определяем массив $$$a'$$$ как массив, полученный после разворота массива $$$a$$$, т.е. $$$a' = [a_n, a_{n-1}, \ldots , a_1]$$$.

Красота массива $$$a$$$ определяется как $$$min(\text{LIS}(a),\text{LIS}(a'))$$$.

Ваша задача  — определить максимально возможную красоту массива $$$a$$$, если вы можете произвольно переставить местами элементы массива $$$a$$$.

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

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

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

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

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

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

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

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

В первом наборе входных данных $$$a$$$ = $$$[6, 6, 6]$$$ и $$$a'$$$ = $$$[6, 6, 6]$$$. $$$\text{LIS}(a) = \text{LIS}(a')$$$ = $$$1$$$. Следовательно, красота равна $$$min(1, 1) = 1$$$.

Во втором наборе входных данных $$$a$$$ может быть перестроено в $$$[2, 5, 4, 5, 4, 2]$$$. Тогда $$$a'$$$ = $$$[2, 4, 5, 4, 5, 2]$$$. $$$\text{LIS}(a) = \text{LIS}(a') = 3$$$. Следовательно, красота равна $$$3$$$, и можно показать, что это максимально возможная красота.

В третьем наборе входных данных $$$a$$$ может быть перестроено в $$$[1, 2, 3, 2]$$$. Тогда $$$a'$$$ = $$$[2, 3, 2, 1]$$$. $$$\text{LIS}(a) = 3$$$, $$$\text{LIS}(a') = 2$$$. Следовательно, красота равна $$$min(3, 2) = 2$$$ и можно показать, что $$$2$$$  — это максимально возможная красота.