특정 수열이 순증가하는 부분을 LIS(Longest Increasing Sequence = 증가 부분 수열)라고 합니다. 주어진 수열에서 증가 부분 수열 중 가장 길이가 긴 것의 길이를 반환하는 프로그램을 작성하십시오.

입력

첫 줄에 수열에 포함되는 원소의 수

다음 줄에 원소의 수 만큼 공백으로 구분하여 수 나열

출력

수열에서 가장 긴 증가 부분 수열의 길이를 출력한다.