Longest Increasing Subsequence

You are given a sequence of book widths. Your task is to compute the length of the longest strictly increasing subsequence in the given sequence.

Given a sequence \(a_1, a_2, \dots, a_n\), find the largest \(k\) such that there exist indices \(1 \le i_1 < i_2 < \dots < i_k \le n\) with \(a_{i_1} < a_{i_2} < \dots < a_{i_k}\).

Note: The increasing subsequence does not need to be contiguous.

inputFormat

The first line contains an integer \(n\) representing the number of books. The second line contains \(n\) integers separated by spaces representing the widths of the books.

If \(n = 0\), the sequence is empty.

outputFormat

Output a single integer denoting the length of the longest strictly increasing subsequence.

## sample

6
5 3 4 8 6 7

4

</p>