Longest Wave

You are given an array of integers. A wave is defined as a contiguous subarray where the differences between consecutive elements alternate in sign. Formally, for a subarray a[l..r] (with r - l + 1 ≥ 2), let (d_i = a_{i+1} - a_i) for (l \leq i < r). The subarray is a wave if for every consecutive pair (d_i, d_{i+1}), we have (d_i \cdot d_{i+1} < 0). If the array contains only a single element, consider its wave length as 1. Otherwise, if no valid wave (of length at least 2) exists, the answer is 0.

Your task is to determine the length of the longest wave in the given array. Input is taken from standard input and output should be printed to standard output.

inputFormat

The first line of input contains an integer (n) denoting the number of elements in the array. The second line contains (n) space-separated integers, which are the elements of the array.

outputFormat

Print a single integer representing the length of the longest wave found in the array. If there is no wave of length at least 2, print 0.## sample

6
1 3 2 5 4 6

6