가장 긴 증가 부분 수열

첫 줄에 수열의 길이 n (1 이상 8000 이하) 이 주어집니다. 둘째 줄에 n개의 정수가 주어집니다 (1 이상 1000000000 이하).

엄격히 증가하는 부분 수열(원소를 골라 순서를 유지한 것) 중 가장 긴 것의 길이를 출력하세요. 예를 들어 10 20 10 30 20 50 에서 10 20 30 50 이 길이 4로 가장 깁니다.

예시

입력

6
10 20 10 30 20 50

출력

4