eolymp
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$).
Time limit 1 second
Memory limit 128 MiB
Input example #1
4
6 5 2 4
Output example #1
6
Author Anton Tsypko
Source Ukrainian Olympiad in Informatics 2020/2021, I stage