Longest Increasing Subsequence

You are given an integer sequence. Your task is to compute the length of the Longest Increasing Subsequence (LIS) in this sequence. An increasing subsequence is a sequence that can be derived from the original sequence by deleting some or no elements without changing the order, and each element in the subsequence is strictly greater than its predecessor.

Formally, given a sequence of numbers \(a_1, a_2, \ldots, a_n\), find the maximum integer \(L\) such that there exists indices \(1 \leq i_1 < i_2 < \ldots < i_L \leq n\) satisfying \[ a_{i_1} < a_{i_2} < \cdots < a_{i_L}. \]

If the sequence is empty, the length of the LIS is defined as 0.

inputFormat

The input is read from stdin and consists of two lines:

1. The first line contains a single integer \(n\) representing the number of elements in the sequence.
2. The second line contains \(n\) space-separated integers representing the elements of the sequence. If \(n = 0\), the second line will be empty.

outputFormat

Output a single integer to stdout which is the length of the longest increasing subsequence in the given sequence.

6
5 1 6 2 7 3

3