Columns
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.
Input data
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.
Output data
Print one number — the minimum number of colors required to paint all cubes so that all substrings and columns have different colors.
Examples
4 6 5 2 4
6
Note
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).