A survey sled records n sand-height readings across a dune field, in travel order. A peak profile is a subsequence of readings (not necessarily adjacent), in travel order, whose heights strictly increase up to a single peak reading and then strictly decrease. A purely strictly-increasing subsequence counts as a peak profile (its peak is the last reading), and so does a purely strictly-decreasing one (its peak is the first reading). A single reading is a peak profile of length 1. Report the maximum number of readings in a peak profile.
Input format
Line 1: an integer n.
Line 2: n space-separated integers, the heights in travel order.
Output format
A single integer: the length of the longest bitonic subsequence.
Constraints
- 1 <= n <= 2000
- -1000000000 <= height <= 1000000000