Назовем последовательность целых чисел красивой, если выполняются следующие условия:
Например, $$$[1, 2]$$$, $$$[42]$$$, $$$[1, 4, 2, 4, 7]$$$ и $$$[1, 2, 4, 8]$$$ являются красивыми, но $$$[2, 2, 4]$$$ и $$$[1, 3, 5, 3]$$$ — нет.
Напомним, что подпоследовательность — это последовательность, которую можно получить из другой последовательности, удалив некоторые элементы (возможно, ни одного), не изменяя порядок оставшихся элементов.
Вам дан целочисленный массив $$$a$$$ размером $$$n$$$. Найдите самую длинную красивую подпоследовательность массива $$$a$$$ и выведите ее длину.
Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следуют $$$t$$$ независимых наборов входных данных.
Первая строка каждого набора содержит одно целое число $$$n$$$ ($$$1 \le n \le 5 \cdot 10^5$$$) — длину массива $$$a$$$.
Вторая строка каждого набора содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^6$$$) – массив $$$a$$$.
Дополнительное ограничение на входные данные: сумма $$$n$$$ по всем наборам не превышает $$$5 \cdot 10^5$$$.
Для каждого набора выведите одно целое число — длину самой длинной красивой подпоследовательности массива $$$a$$$.
514251 2 3 4 566 5 4 3 2 171 1 3 4 2 3 462 3 1 1 2 4
1 5 1 5 3
