A rover logs n floor-depth readings while crossing a canyon, in travel order. A basin profile is a subsequence of readings (not necessarily adjacent), in travel order, whose depths strictly decrease down to a single lowest reading and then strictly increase. A purely strictly-decreasing subsequence counts as a basin profile (its low point is the last reading), and so does a purely strictly-increasing one (its low point is the first reading). A single reading is a basin profile of length 1. Report the maximum number of readings in a basin profile.
Input format
Line 1: an integer n.
Line 2: n space-separated integers, the depths in travel order.
Output format
A single integer: the length of the longest valley subsequence.
Constraints
- 1 <= n <= 2000
- -1000000000 <= depth <= 1000000000