수열에서 몇 개의 수를 골라(순서는 그대로 두고) 점점 커지는 수열을 만들려고 해요. 예를 들어 10 20 10 30 20 50에서는 10 20 30 50을 골라 길이 4를 만들 수 있어요. 만들 수 있는 가장 긴 오르막 수열의 길이를 구하세요. 같은 수는 커지는 것이 아니에요.
입력
첫째 줄에 수열의 길이 N이 주어져요. (1 ≤ N ≤ 1,000) 둘째 줄에 N개의 정수가 공백으로 구분되어 주어져요. (0 ≤ 수 ≤ 1,000,000)
출력
가장 긴 오르막 수열의 길이를 출력해요.