Takahashi's Tree Collection

Takahashi loves to collect trees, but he will only collect them if the heights are in strictly increasing order. Given a sequence of tree heights, your task is to determine the maximum number of trees he can collect such that each tree collected has a height larger than the previous one. This is equivalent to finding the length of the longest increasing subsequence (LIS) of the given sequence.

The recurrence relation used in dynamic programming is defined as follows: [ dp[i] = 1 + \max_{0 \leq j < i \text{ and } H[j] < H[i]} dp[j] ]

Your program should read the input from standard input and write the result to standard output.

inputFormat

The input consists of two lines. The first line contains an integer (N) representing the number of trees. The second line contains (N) space-separated integers representing the heights of the trees.

outputFormat

Output a single integer: the maximum number of trees that can be collected in an increasing order.## sample

5
1 3 2 5 4

3