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

예를 들어, 수열 \(A = \{1, 3, 2, 9, 7, 8, 5, 10\}\) 인 경우에 가장 긴 증가하는 부분 수열은 \(A = \{1, 3, 7, 8, 10\}\) 이고, 길이는 5이다.

입력

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

출력

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

제한사항

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

예제 입력 1

9
1 3 2 9 7 8 5 10 6

예제 출력 1

5