Longest Increasing Subsequence

Given a sequence of integers representing the heights of blocks, determine the length of the longest strictly increasing subsequence.

Formally, given a sequence \(A = [a_1, a_2, \dots, a_n]\), find the maximum integer \(k\) such that there exist indices \(1 \le i_1 < i_2 < \dots < i_k \le n\) with the property that \(a_{i_1} < a_{i_2} < \cdots < a_{i_k}\).

Example: For the input sequence [1, 2, 1, 5, 3, 4], the longest strictly increasing subsequence is [1, 2, 3, 4] with length 4.

inputFormat

The input is read from standard input (stdin). The first line contains a single integer (n) ((1 \le n \le 10^5)) representing the number of blocks. The second line contains (n) space-separated integers representing the heights of the blocks.

outputFormat

Output a single integer to standard output (stdout) which is the length of the longest strictly increasing subsequence.## sample

6
1 2 1 5 3 4

4