Write an efficient algorithm for the following problem, briefly describe why it is a correct algorithm, and analyze the time complexity. If you believe there is no polynomial-time algorithm, then describe the reason.

• Problem: Longest valley subsequence
• Input: An array A[1...n] of positive integers.
• Output: The length of the longest valley subsequence. A valley subsequence is first decreasing and then increasing.
• Example: Input: A = [1,7,2,3,1,5,4,6,8]. Output: 6 (because of 7,3,1,4,6,8)