Codeforces Round 628 (Div. 2) |
---|
Закончено |
У Ехаба есть массив $$$a$$$ длины $$$n$$$. У него достаточно свободного времени, чтобы создать новый массив, состоящий из $$$n$$$ копий старого массива, записанных последовательно. Чему равна длина самой длинной возрастающей подпоследовательности нового массива?
Последовательность $$$a$$$ является подпоследовательностью массива $$$b$$$, если $$$a$$$ можно получить из $$$b$$$, удалив несколько (возможно, ноль или все) элементов. Самая длинная возрастающая подпоследовательность массива это самая длинная подпоследовательность, все элементы которой упорядочены в строго возрастающем порядке.
Первая строка содержит целое число $$$t$$$ — количество наборов входных данных. Далее следуют описания наборов входных данных.
Первая строка описания каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 10^5$$$) — количество элементов в массиве $$$a$$$.
Вторая строка содержит $$$n$$$ целых чисел, разделенных пробелом $$$a_1$$$, $$$a_2$$$, $$$\ldots$$$, $$$a_{n}$$$ ($$$1 \le a_i \le 10^9$$$) — элементы массив $$$a$$$.
Сумма $$$n$$$ по всем наборам входных данных не превышает $$$10^5$$$.
Для каждого набора входных данных, выведите длину самой длинной возрастающей подпоследовательности $$$a$$$, если вы объедините ее с собой $$$n$$$ раз.
2 3 3 2 1 6 3 1 4 1 5 9
3 5
В первом наборе входных данных примера, новый массив равен $$$[3,2,\textbf{1},3,\textbf{2},1,\textbf{3},2,1]$$$. Самая длинная возрастающая подпоследовательность в нем выделена жирным.
Во втором наборе входных данных примера, самая длинная возрастающая подпоследовательность равна $$$[1,3,4,5,9]$$$.
Название |
---|