Задається послідовність з \(N\) цілих чисел: \(A = \{ A_1, A_2, \cdots, A_N \}\).

Для кожного з цих \(N\) цілих чисел ми виберемо колір і зафарбуємо ціле число цим кольором.

Тут має бути виконана така умова:

• якщо \(A_i\) і \(A_j\) (\(i < j\)) пофарбовані одним кольором, то \(A_i < A_j\).

Знайдіть мінімальну кількість кольорів, необхідну для виконання умови.

Формат вхідних даних

Перший рядок вхідного потоку містить ціле число \(N\) (\(1 \le N \le 10^5\)).

Наступний рядок містить цілі числа \(A_i\) (\(0 \le A_i \le 10^9\)), які розділяються пропуском.

Формат вихідних даних

У вихідний потік вивести шукану мінімальну кількість.

Примітка

До прикладу 1:

Ми можемо задовольнити умову двома кольорами, наприклад, пофарбувавши 2 і 3 червоним і 1, 4 і 5 синім.

Приклад вхідних даних

5
2
1
4
5
3

Приклад вихідних даних

2

Приклад вхідних даних

4
0
0
0
0

Приклад вихідних даних

4