eolymp
bolt
Try our new interface for solving problems
Problems

Columns

Columns

Time limit 1 second
Memory limit 128 MiB

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

Input example #1
4
6 5 2 4
Output example #1
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).

Author Anton Tsypko
Source Ukrainian Olympiad in Informatics 2020/2021, I stage