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

증가하는 부분 수열의 정의 수열 \(A = (a_1, a_2, \dots, a_N)\)에서 일부 원소를 골라 만든 수열 \((a_{i_1}, a_{i_2}, \dots, a_{i_k})\) (\(1 \le i_1 < i_2 < \dots < i_k \le N\))가 다음 두 조건을 모두 만족해야 한다.

1. 순서 유지 (부분 수열): 원소들은 원래 수열에서의 순서(인덱스)를 유지해야 한다. (원소들이 서로 연속해 있을 필요는 없다.)
2. 엄격한 증가 (증가 수열): 선택된 원소들은 뒤로 갈수록 반드시 엄격하게 커져야 한다. 즉, \(a_{i_1} < a_{i_2} < \dots < a_{i_k}\) 를 만족해야 한다. (값이 같은 경우는 인정하지 않는다.)

예를 들어, 수열 \(A = \{1, 3, 2, 9, 7, 8, 5, 10\}\) 이 주어진 경우:

• \(\{1, 3, 9, 10\}\) 은 증가하는 부분 수열이다. (길이 4)
• \(\{1, 3, 7, 8, 10\}\) 은 증가하는 부분 수열이다. (길이 5)
• \(\{1, 3, 2, 5\}\) 는 \(3 \to 2\)로 감소하는 구간이 있으므로 증가하는 부분 수열이 아니다.

이 중 길이가 가장 긴 부분 수열은 \(\{1, 3, 7, 8, 10\}\) (또는 \(\{1, 2, 7, 8, 10\}\)) 이며, 그 길이는 5이다.

입력

첫째 줄에 수열 \(A\)의 크기 \(N\) (\(1 \le N \le 1000\))이 주어진다. 둘째 줄에는 수열 \(A\)를 이루고 있는 \(A_i\)가 순서대로 주어진다. (\(1 \le A_i \le 1000\))

출력

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

제한사항

• \(1 \le N \le 1000\)
• \(1 \le A_i \le 1000\)

예제 입력 1

9
1 3 2 9 7 8 5 10 6

예제 출력 1

5