Назовем массив $$$b$$$ длины $$$m$$$ хорошим, если выполняются следующие условия:
Например, массив $$$[1,1,3,3,5]$$$ является хорошим (где перестановка $$$p=[2,1,5,3,4]$$$ удовлетворяет второму требованию), но массив $$$[1,1,2]$$$ не является.
Обратите внимание, что пустой массив считается хорошим.
Вам дан массив $$$a$$$ размером $$$n$$$. Найдите длину самой длинной хорошей подпоследовательности$$$^{\text{†}}$$$ массива $$$a$$$.
$$$^{\text{∗}}$$$Перестановкой длины $$$m$$$ является массив, состоящий из $$$m$$$ различных целых чисел от $$$1$$$ до $$$m$$$ в произвольном порядке. Например, $$$[2,3,1,5,4]$$$ — перестановка, но $$$[1,2,2]$$$ не перестановка ($$$2$$$ встречается в массиве дважды) и $$$[1,3,4]$$$ тоже не перестановка ($$$m=3$$$, но в массиве встречается $$$4$$$).
$$$^{\text{†}}$$$Последовательность $$$c$$$ является подпоследовательностью $$$d$$$, если $$$c$$$ может быть получена из $$$d$$$ удалением нескольких (возможно, ни одного или всех) элементов на произвольных позициях.
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит целое число $$$n$$$ ($$$1 \leq n \leq 15\,000$$$) — длина массива $$$a$$$.
Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \leq a_i \leq n$$$) — массив $$$a$$$.
Гарантируется, что сумма $$$n^2$$$ по всем наборам входных данных не превосходит $$$15\,000^2$$$.
Для каждого набора входных данных на отдельной строке выведите длину самой длинной хорошей подпоследовательности массива $$$a$$$.
551 1 3 3 531 1 242 2 2 271 2 4 2 4 6 211
5 2 0 5 1
В первом наборе входных данных вся последовательность является хорошей.
Во втором наборе входных данных самой длинной хорошей подпоследовательностью является $$$[1,2]$$$.
