Дано n столбиков из кубиков, i-ый имеет высоту ai. Найдите наименьшее количество цветов, достаточных для покраски всех кубиков так, чтобы во всех подстроках и столбиках были разные цвета. Обратите внимание, что подстрока — это горизонтальная последовательность кубиков, идущих подряд, то есть без пропусков.
Первая строка содержит одно целое число n (1≤n≤1000) — количество столбиков.
Вторая строка содержит n целых чисел a1,a2,…,an (1≤ai≤1000) — высота i-го столбика.
Выведите одно число — минимальное количество цветов, необходимых для покраски всех кубиков так, чтобы во всех подстроках и столбцах были разные цвета.
Одно из возможных решений:
Обратите внимание, что в третьей строке снизу могут присутствовать два одинаковых цвета, если между ними пустое место (третий столбик имеет высоту 2).