Longest Increasing Subsequence

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

A subsequence is a sequence that can be derived from the array by removing some elements while keeping the order of the remaining elements intact. The increasing subsequence is one in which every element is strictly greater than its preceding element.

Input Format: The first line contains an integer n representing the number of elements. The second line contains n integers separated by spaces.

Output Format: A single integer that denotes the length of the longest increasing subsequence.

For example, for the input:

8
10 9 2 5 3 7 101 18

the output is 4.

Note: If the array is empty, output 0.

inputFormat

The input is read from standard input (stdin) and consists of:

1. An integer n in the first line, representing the number of elements in the array.
2. The second line contains n space-separated integers.

outputFormat

The output should be written to standard output (stdout). It consists of a single integer representing the length of the longest increasing subsequence in the input array.

## sample

8
10 9 2 5 3 7 101 18

4