Столбики

Дано $n$ столбиков из кубиков, $i$-ый имеет высоту $a_i$. Найдите наименьшее количество цветов, достаточных для покраски всех кубиков так, чтобы во всех подстроках и столбиках были разные цвета. Обратите внимание, что подстрока — это горизонтальная последовательность кубиков, идущих подряд, то есть без пропусков.

Giriş verilənləri

Первая строка содержит одно целое число $n$ ($1\le n\le 1000$) — количество столбиков.

Вторая строка содержит $n$ целых чисел $a_1,a_2,\dots ,a_n$ ($1\le a_i\le 1000$) — высота $i$-го столбика.

Çıxış verilənləri

Выведите одно число — минимальное количество цветов, необходимых для покраски всех кубиков так, чтобы во всех подстроках и столбцах были разные цвета.

Nümunələr

Qeyd

Одно из возможных решений:

Обратите внимание, что в третьей строке снизу могут присутствовать два одинаковых цвета, если между ними пустое место (третий столбик имеет высоту $2$).