Longest Increasing Subsequence

You are given a sequence of integers. Your task is to find the length of the longest strictly increasing subsequence (LIS) in the sequence.

A subsequence is a sequence that can be derived from the original sequence by deleting some or no elements without changing the order of the remaining elements. The longest increasing subsequence is defined as the subsequence in which every element is greater than the previous element and its length is maximized.

Mathematically, if the input sequence is \(a_1, a_2, \dots, a_n\), you need to determine the maximum \(k\) such that there exists indices \(1 \leq i_1 < i_2 < \dots < i_k \leq n\) where \(a_{i_1} < a_{i_2} < \cdots < a_{i_k}\).

inputFormat

The first line of input contains a single integer (n) (the number of elements in the sequence). The second line contains (n) space-separated integers representing the elements of the sequence.

outputFormat

Output a single integer representing the length of the longest strictly increasing subsequence in the given sequence.## sample

6
5 2 8 6 3 6

3