Longest Increasing or Decreasing Subsequence

You are given a sequence of integers representing the magical strengths of potions. Your task is to determine the length of the longest subsequence (not necessarily contiguous) that is strictly increasing or strictly decreasing.

Formally, given an array \(A\) of length \(n\), find the maximum \(k\) such that there exists indices \(1 \le i_1 < i_2 < \cdots $$A_{i_1} < A_{i_2} < \cdots < A_{i_k}$$

or

$$A_{i_1} > A_{i_2} > \cdots > A_{i_k}.$$

You can solve this problem by using dynamic programming with a time complexity of \(O(n^2)\). In particular, you can compute the longest increasing subsequence (LIS) and the longest decreasing subsequence (LDS) separately, and then take the maximum of the two.

## inputFormat

The first line contains an integer \(n\) representing the number of potions. The second line contains \(n\) space-separated integers denoting the strength of each potion. If \(n = 0\), the second line will be empty.

## outputFormat

Output a single integer: the length of the longest strictly increasing or strictly decreasing subsequence.

## sample

8
5 2 8 6 3 6 9 7

4

$$