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) in the array.

A subsequence is a sequence that can be derived from the original array by deleting some or no elements without changing the order of the remaining elements.

For a given array \(a_1, a_2, \dots, a_n\), a subsequence \(a_{i_1}, a_{i_2}, \dots, a_{i_k}\) is called strictly increasing if \(a_{i_1} < a_{i_2} < \cdots < a_{i_k}\). The task is to find the maximum value of \(k\) for which such a subsequence exists.

inputFormat

The input is read from standard input (stdin) and is structured as follows:

• The first line contains a single integer n (0 \(\le n \le 10^5\)) denoting the number of elements in the array.
• The second line contains n space-separated integers representing the array elements.

outputFormat

Output a single integer to standard output (stdout) which represents the length of the longest strictly increasing subsequence of the array.

## sample

8
10 22 9 33 21 50 41 60

5

</p>