Longest Increasing or Decreasing Subsequence

You are given a sequence of n integers representing the heights of trees. Your task is to find the length of the longest subsequence of trees such that the heights are strictly increasing or strictly decreasing.

A subsequence is a sequence derived from the original sequence by deleting some or no elements without changing the order of the remaining elements.

Formally, let \(a_1, a_2, \dots, a_n\) be the sequence of tree heights. You need to determine the maximum \(k\) such that there exists indices \(1 \le i_1 < i_2 < \dots < i_k \le n\) where either

\(a_{i_1} < a_{i_2} < \cdots < a_{i_k}\) or \(a_{i_1} > a_{i_2} > \cdots > a_{i_k}\).

If there is no valid subsequence (for example, when all numbers are equal) then the answer is 1.

inputFormat

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 which is the length of the longest subsequence that is strictly increasing or strictly decreasing.

1
10

1