Search for the maximum length of a strictly increasing subsequence

C# Medium loops

Task «Search for the maximum length of a strictly increasing subsequence»

Write a program that finds the maximum length of a strictly increasing subsequence in a sequence of integers. The sequence may contain duplicate elements. The sequence length ranges from 1 to 10^5, and the elements range from -10^9 to 10^9. The solution must use a single pass through the data.

Input Format

The first line contains an integer N — the number of elements. The second line contains N integers separated by spaces.

Output Format

One integer — the maximum length of a strictly increasing subsequence.

Examples

Example 1

INPUT

5
5 4 3 2 1

OUTPUT

1

Example 2

INPUT

6
1 3 5 2 4 6

OUTPUT

3

main.cs