Longest Increasing Subsequence

You are given an array of n integers. Your task is to compute the length of the longest strictly increasing subsequence in the array.

A subsequence is a sequence that can be derived from an array by deleting some or no elements without changing the order of the remaining elements. Formally, given an array \(a_1, a_2, \dots, a_n\), find the maximum length \(L\) such that there exists indices \(1 \le i_1 < i_2 < \dots < i_L \le n\) with \(a_{i_1} < a_{i_2} < \dots < a_{i_L}\).

The input will be read from stdin and the output should be written to stdout.

inputFormat

The input consists of two lines:

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

outputFormat

Output a single integer representing the length of the longest strictly increasing subsequence of the array.

## sample

0

0

</p>