Longest Increasing Subsequence

Given an array of integers, your task is to find the length of the longest strictly increasing subsequence. An increasing subsequence is a sequence formed from the array by deleting some (or no) elements without changing the order of the remaining elements.

For instance, if the input array is [10, 22, 9, 33, 21, 50, 41, 60, 80], one of the longest increasing subsequences is [10, 22, 33, 50, 60, 80] and its length is 6.

Mathematically, given an array \(A = [a_1, a_2, \dots, a_n]\), you are required to compute the maximum integer \(k\) such that there exist indices \(1 \le i_1 < i_2 < \dots < i_k \le n\) with \(a_{i_1} < a_{i_2} < \dots < a_{i_k}\).

inputFormat

The first line contains an integer (n) representing the number of elements in the array. The second line contains (n) space-separated integers. If (n=0), the second line is omitted.

outputFormat

Print one integer — the length of the longest strictly increasing subsequence.## sample

9
10 22 9 33 21 50 41 60 80

6