최대 부분 증가 수열

N개의 정수로 이루어진 수열에서 가장 긴 증가하는 부분 수열(LIS, Longest Increasing Subsequence)의 길이를 구하라. O(N²) DP로 구현하라.

부분 수열은 원래 수열에서 순서를 유지하며 일부 원소를 제거해 만든다. 증가하는 부분 수열은 선택한 원소가 왼쪽에서 오른쪽으로 갈수록 순증가해야 한다.

예를 들어 [10, 9, 2, 5, 3, 7, 101, 18]에서 LIS는 [2, 5, 7, 101]로 길이 4이다.

입력

첫째 줄에 수열의 크기 N이 주어진다.
둘째 줄에 N개의 정수가 공백으로 구분되어 주어진다.

• 1 ≤ N ≤ 1,000
• 1 ≤ 각 정수 ≤ 1,000

출력

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

예제 입력 1

8
10 9 2 5 3 7 101 18

예제 출력 1

4