가장 긴 증가하는 부분 수열

수열 $A$가 주어졌을 때, 가장 긴 증가하는 부분 수열의 길이를 구하는 프로그램을 작성하시오.

부분 수열은 $A$에서 원소를 0개 이상 지우고 남은 원소를 원래 순서대로 이어 붙인 수열이다. 증가하는 부분 수열은 앞에서 뒤로 가면서 값이 항상 엄격하게 커지는 부분 수열이므로, 값이 같은 원소를 두 개 고를 수 없다.

예를 들어 $A = (10, 20, 10, 30, 20, 50)$이면 10, 20, 30, 50을 고른 것이 가장 긴 증가하는 부분 수열이고, 길이는 4이다.

첫째 줄에 수열 $A$의 크기 $N$이 주어진다. ($1 \le N \le 1000$)

둘째 줄에 수열 $A$를 이루는 $A_1, A_2, \dots, A_N$이 공백으로 구분되어 주어진다. ($1 \le A_i \le 1000$)

첫째 줄에 수열 $A$의 가장 긴 증가하는 부분 수열의 길이를 출력한다.