Longest Increasing Subsequence

Given an array of integers, your task is to compute the length of the longest strictly increasing subsequence (LIS).

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. More formally, for an array \( A = [a_1, a_2, \dots, a_n] \), a subsequence \( [a_{i_1}, a_{i_2},\dots, a_{i_k}] \) (with \( 1 \le i_1 < i_2 < \dots < i_k \le n \)) is increasing if \[ a_{i_1} < a_{i_2} < \dots < a_{i_k}. \]

Your goal is to find the maximum value of \( k \) such that an increasing subsequence of length \( k \) exists.

The classic approach uses dynamic programming where the state \( dp[i] \) represents the length of the longest increasing subsequence ending at index \( i \). The state transition is given by:

[ dp[i] = 1 + \max_{0 \le j < i \text{ and } a_j < a_i}(dp[j]) ]

If there is no such \( j \), then \( dp[i] = 1 \). Your program should ultimately output the maximum value among all \( dp[i] \).

inputFormat

The input is given via standard input and has the following format:

• The first line contains an integer \( n \) representing the number of elements in the sequence.
• If \( n > 0 \), the second line contains \( n \) space-separated integers representing the sequence.

outputFormat

Output the length of the longest strictly increasing subsequence to standard output.

## sample

6
5 2 8 6 3 6

3

</p>