У Nezzar есть \(n\) шаров, пронумерованных числами \(1, 2, \ldots, n\). На них написаны числа \(a_1, a_2, \ldots, a_n\), соответственно. Числа на этих шарах образуют неубывающую последовательность, то есть \(a_i \leq a_{i+1}\) для всех \(1 \leq i < n\).
Nezzar хочет покрасить эти шары в минимальное количество цветов так, чтобы следующее условие было выполнено.
- Для любого цвета числа будут образовывать строго возрастающую последовательность, если он оставит только шары этого цвета и уберет все остальные шары.
Обратите внимание, что последовательность длины не больше \(1\) считается строго возрастающей последовательностью.
Помогите Nezzar определить минимальное количество цветов.
Выходные данные
Для каждого набора входных данных выведите минимальное количество цветов, которое Nezzar может использовать.
Примечание
Будем каждому цвету сопоставлять свое число. Тогда:
В первом наборе входных данных одна из оптимальных раскрасок это \([1,2,3,3,2,1]\).
Во втором наборе входных данных одна из оптимальных раскрасок это \([1,2,1,2,1]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
6
1 1 1 2 3 4
5
1 1 2 2 3
4
2 2 2 2
3
1 2 3
1
1
|
3
2
4
1
1
|