Longest Increasing Subsequence of Book Thickness

Given a sequence of integers representing the thicknesses of books, your task is to find the length of the longest increasing subsequence. A subsequence is derived from the original sequence by deleting some or no elements without changing the order of the remaining elements.

Formally, for a sequence \(a_1, a_2, \ldots, a_n\), an increasing subsequence is a sequence \(a_{i_1}, a_{i_2}, \ldots, a_{i_k}\) such that \(a_{i_1} < a_{i_2} < \cdots < a_{i_k}\). Your goal is to determine the maximum possible \(k\).

inputFormat

The first line contains an integer (n) representing the number of books. The second line contains (n) space-separated integers, each denoting the thickness of a book.

outputFormat

Output a single integer representing the length of the longest increasing subsequence.## sample

6
5 3 4 8 6 7

4