Longest Increasing Subsequence

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

A subsequence is obtained by deleting some or no elements from the original array without changing the order of the remaining elements. Formally, for a given sequence (a_1, a_2, \ldots, a_n), a subsequence is defined by indices (1 \leq i_1 < i_2 < \cdots < i_k \leq n) such that (a_{i_1} < a_{i_2} < \cdots < a_{i_k}). The goal is to find the maximum possible value of (k).

inputFormat

The first line of input contains a single integer (n) representing the number of elements in the array. The second line contains (n) space-separated integers which are the elements of the array.

outputFormat

Output a single integer which is the length of the longest strictly increasing subsequence in the array.## sample

5
2 2 2 3 3

2