Longest Increasing Subsequence

Problem Description

You are given an array of integers. Your task is to find the length of the longest strictly increasing subsequence (LIS) in 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. In other words, for an array A of length n, find the maximum length L such that there exists indices 1 \leq i₁ < i₂ < ... < i_L \leq n with:

$$A_{i_1} < A_{i_2} < \cdots < A_{i_L}.$$

Consider a dynamic programming solution with a time complexity of \(O(n^2)\), which is acceptable given the constraints.

inputFormat

Input Format

The first line contains a single integer \(n\) which denotes the number of elements in the array.

The second line contains \(n\) space-separated integers representing the array.

outputFormat

Output Format

Output a single integer which is the length of the longest strictly increasing subsequence in the array.

## sample

8
10 9 2 5 3 7 101 18

4