Longest Increasing or Decreasing Subsequence

You are given a conveyor belt containing n objects, each represented by an integer. You can choose a subsequence of objects that is either strictly increasing or strictly decreasing.

Your task is to determine the maximum length among these two types of subsequences.

This problem can be described by the following formula:

$$ ans = \max(\text{LIS},\,\text{LDS}) $$

where LIS is the length of the longest strictly increasing subsequence and LDS is the length of the longest strictly decreasing subsequence.

inputFormat

The first line contains a single integer ( n ) representing the number of objects on the conveyor belt. The second line contains ( n ) space-separated integers denoting the values of the objects.

outputFormat

Output a single integer which is the maximum length of either a strictly increasing or a strictly decreasing subsequence.## sample

6
5 3 4 8 6 7

4