Problem description

Jak każdy wprawiony uczeń wie skrót ℒℐ𝒮 pochodzi od zagadnienia algorytmicznego Najdłuższy podciąg rosnący – najdłuższy niekoniecznie spójny podciąg rosnących elementów ciągu. Natomiast akcja historyjki tego zadania dzieje się w Bajtocji, gdzie słowo ℒℐ𝒮 oznacza zarówno zwierzątko, jak i najdłuższy podciąg rosnący.

Farmę Bajtazara nawiedza ostatnio tytułowy Rudy Lisek. Z powodu strat materialnych Bajtazarowi nie przypadły do gustu wizyty rudego przyjaciela, postanowił on więc złapać Liska i kulturalnie mu wytłumaczyć, że nie jest mile widzianym gościem na jego farmie. Niestety Rudy Lisek schował się w permutacji liczb i Bajtazar nie jest w stanie go dostrzec.

I tutaj pojawia się twoje zadanie – odszukanie Rudego Liska w permutacji P. Bajtazar poprosił cię o samą długość Rudego Liska, bowiem zdaje on sobie sprawę, z tego, że wskazanie jego dokładnej lokalizacji może być problematyczne.

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba naturalna N oznaczająca długość permutacji P, W drugim wierszu wejścia znajduje się N liczb naturalnych P_i, pooddzielanych pojedynczymi odstępami i oznaczających kolejne elementy permutacji P.

Wyjście

Twój program powinien wypisać na wyjście jedną liczbę naturalną – długość najdłuższego podciągu rosnącego w permutacji P.

Ograniczenia

1 ≤ N ≤ 1 000 000, 1 ≤ P_i ≤ N

Przykład

5
2 1 3 5 4

3

5
4 3 2 5 1

2