A signal monitor records n samples. A wiggle run is a subsequence whose consecutive differences strictly alternate between positive and negative (up, down, up, ... or down, up, down, ...). A single sample is a wiggle run of length 1, and two samples with different values form one of length 2. Report the length of the longest wiggle run that can be selected as a subsequence (elements keep their original order but need not be adjacent).
Input format
Line 1: an integer n.
Line 2: n space-separated integers, the samples in order.
Output format
A single integer: the length of the longest wiggle subsequence.
Constraints
- 1 ≤ n ≤ 100000
- -1000000000 ≤ each sample ≤ 1000000000