Given n columns of cubes, the i -th has height ai. 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.
The first line contains one integer n (1≤n≤1000) — the number of columns.
The second line contains n integers a1,a2,…,an (1≤ai≤1000) — the height of the i-th column.
Print one number — the minimum number of colors required to paint all cubes so that all substrings and columns have different colors.
One of the possible solutions:
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).