Longest Increasing Subsequence

You are given an array of N integers. Your task is to determine the length of the longest strictly increasing subsequence (LIS) within the array.

A subsequence is a sequence that can be derived from the array by deleting some or no elements without changing the order of the remaining elements. The sequence is strictly increasing if each element is greater than the previous one.

The mathematical definition can be written in LaTeX as:

\(\text{LIS}(a) = \max\{ k : \exists\, i_1 < i_2 < \cdots < i_k \text{ such that } a_{i_1} < a_{i_2} < \cdots < a_{i_k}\}\)

inputFormat

The first line contains a single integer N, the number of elements in the array.

The second line contains N space-separated integers representing the array elements.

outputFormat

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

1
1

1