가장 긴 감소하는 부분 수열

수열 $A$가 주어진다. $A$의 가장 긴 감소하는 부분 수열의 길이를 구하는 프로그램을 작성하시오.

부분 수열은 $A$에서 원소를 하나 이상 골라 원래 순서를 그대로 유지한 수열이다. 감소하는 부분 수열은 앞의 원소가 바로 뒤의 원소보다 항상 큰 부분 수열이다.

예를 들어 $A = \{10, 30, 10, 20, 20, 10\}$이면 가장 긴 감소하는 부분 수열은 $\{30, 20, 10\}$이고, 길이는 3이다.

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

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

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