Longest Increasing Subsequence

This is a simple dynamic programming template problem.

Given a sequence of n positive integers where \( n \le 5000 \) and each integer is at most \(10^6\), your task is to compute the length of the Longest Increasing Subsequence (LIS) in the sequence.

The Longest Increasing Subsequence is defined as a subsequence of the original sequence (obtained by removing some or no elements without changing the order) such that its elements are in strictly increasing order.

inputFormat

The input consists of two lines:

• The first line contains an integer \( n \) (\( n \le 5000 \)), which is the number of elements in the sequence.
• The second line contains \( n \) positive integers separated by spaces. Each integer does not exceed \(10^6\).

outputFormat

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

sample

6
5 2 8 6 3 6

3