Competitions

# Ukrainian Olympiad in Informatics, I Stage

# Columns

Given $n$ columns of cubes, the $i$ -th has height $a_i$. Find the smallest number of colors sufficient to color all the cubes so that all substrings and columns have different colors. Note that the substring~--- is a horizontal sequence of cubes in a row, that is, without gaps.
\begin{center}
\includegraphics[width=5.25cm, height=5.25cm, bb=0 0 700 900]{https://static.e-olymp.com/content/92/92fac11065f4bc2c06cd443b6ca77282db417292.png}
\end{center}
\InputFile
The first line contains one integer $n$ ($1\leq n\leq 1000$)~--- the number of columns.
The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1\leq a_i\leq 1000$)~--- the height of the $i$-th column.
\OutputFile
Print one number~--- the minimum number of colors required to paint all cubes so that all substrings and columns have different colors.
\Note
One of the possible solutions:
\begin{center}
\includegraphics[width=5.25cm, height=5.25cm, bb=0 0 700 900]{https://static.e-olymp.com/content/aa/aab68cc13221c015a1a10b5cb8874ca13dcdf68e.png}
\end{center}
Note that the third row from the bottom can have two identical colors if there is an empty space between them (the height of the third column is $2$).

Input example #1

4 6 5 2 4

Output example #1

6