У Ехаба есть массив \(a\) длины \(n\). У него достаточно свободного времени, чтобы создать новый массив, состоящий из \(n\) копий старого массива, записанных последовательно. Чему равна длина самой длинной возрастающей подпоследовательности нового массива?
Последовательность \(a\) является подпоследовательностью массива \(b\), если \(a\) можно получить из \(b\), удалив несколько (возможно, ноль или все) элементов. Самая длинная возрастающая подпоследовательность массива это самая длинная подпоследовательность, все элементы которой упорядочены в строго возрастающем порядке.
Выходные данные
Для каждого набора входных данных, выведите длину самой длинной возрастающей подпоследовательности \(a\), если вы объедините ее с собой \(n\) раз.
Примечание
В первом наборе входных данных примера, новый массив равен \([3,2,\textbf{1},3,\textbf{2},1,\textbf{3},2,1]\). Самая длинная возрастающая подпоследовательность в нем выделена жирным.
Во втором наборе входных данных примера, самая длинная возрастающая подпоследовательность равна \([1,3,4,5,9]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
3
3 2 1
6
3 1 4 1 5 9
|
3
5
|