Стовпчики

Дано $n$ стовпчиків з кубиків, $i$-ий має висоту $a_i$. Потрібно знайти мінімальну кількість кольорів, які потрібні, щоб розфарбувати усі кубики так, щоб в усіх підрядках та стовпчиках були різні кольори. Зверніть увагу, що підрядок — це горизонтальна послідовність кубиків, що йдуть підряд, тобто без пропусків.

Input

Перший рядок містить одне ціле число $n$ ($1\le n\le 1000$) — кількість стовпчиків.

Другий рядок містить $n$ цілих чисел $a_1,a_2,\dots ,a_n$ ($1\le a_i\le 1000$) — висота $i$-го стовпчика.

Output

Виведіть одне число — мінімальну кількість кольорів, які потрібні, щоб розфарбувати усі кубики так, щоб в усіх підрядках та стовпчиках були різні кольори.

Examples

Note

Одне з можливих рішень:

Зверніть увагу, що в третьому рядку знизу два однакових кольори, таке може бути, якщо між ними пропуск (третій стовпчик має висоту $2$).