수열 \(A\)가 주어졌을 때, 가장 긴 감소하는 부분 수열(Longest Decreasing Subsequence)의 길이를 구하는 프로그램을 작성하시오.

감소하는 부분 수열의 정의

수열 \(A=(a_1,a_2,\dots,a_N)\)에서 일부 원소를 골라 만든 수열 \((a_{i_1},a_{i_2},\dots,a_{i_k})\)가 다음 두 조건을 모두 만족하면 감소하는 부분 수열이라고 한다.

1. 원소들은 원래 수열에서의 순서를 유지해야 한다. 즉, \(1 \le i_1 < i_2 < \dots < i_k \le N\)이어야 한다. 선택한 원소들이 서로 연속해 있을 필요는 없다.
2. 선택된 원소들은 뒤로 갈수록 반드시 엄격하게 작아져야 한다. 즉, \(a_{i_1}>a_{i_2}>\dots>a_{i_k}\)를 만족해야 한다. 값이 같은 경우는 감소한 것으로 인정하지 않는다.

예를 들어, 수열 \(A=\{9,1,8,2,7,3,6\}\)에서 \(\{9,8,7,6\}\)은 감소하는 부분 수열이다. 반면 \(\{9,1,2\}\)는 \(1<2\)인 부분이 있으므로 감소하는 부분 수열이 아니다.

입력

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

둘째 줄에 수열 \(A\)를 이루는 \(A_i\)가 순서대로 주어진다.

출력

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

제한 사항

• \(1 \le N \le 1,000\)
• \(1 \le A_i \le 1,000\)

예제 입력 1

6
10 30 10 20 20 10

예제 출력 1

3

예제 설명 1

\(\{30,20,10\}\)을 선택하면 길이가 \(3\)인 감소하는 부분 수열을 만들 수 있다. 값이 같은 두 개의 \(20\)은 함께 선택할 수 없다.