Duck Waves

Program time limit: 1 second

Program memory limit: 256 MB

A researcher is observing a line of ducks swimming across a lake.

At regular intervals, the researcher records the height of the duck at the front of the formation, producing a sequence of integers.

A duck wave is a contiguous subsequence that: - first strictly increases then strictly decreases, or - first strictly decreases then strictly increases,

and the two sections are perfectly balanced, meaning they contain the same number of steps.

Adjacent equal values are not allowed within a duck wave. If two adjacent values are equal, the wave ends immediately.

For example, 1 3 5 3 1 is a duck wave of length $5$, since it increases for two steps and then decreases for two steps. Likewise, 7 5 3 5 7 is also a duck wave of length $5$, since it decreases for two steps and then increases for two steps.

Given the recorded sequence, determine the length of the longest duck wave.

A valid duck wave must contain both an increasing section and a decreasing section.

Input

The first line contains an integer $N$ $(1 \le N \le 2\times 10^5)$, the number of recorded heights.

The second line contains $N$ integers $A_1, A_2, \ldots, A_n$ $(-10^9 ≤ A_i ≤ 10^9)$.

Output

Output a single integer: the length of the longest duck wave.

If no valid duck wave exists, output $0$.

Examples

Example 1

Input

11
1 3 5 7 5 3 1 2 3 2 1

Output

7

Explanation

The longest duck wave is 1 3 5 7 5 3 1, which increases for three steps then decreases for three steps, forming a balanced duck wave of length $7$.

The later wave 1 2 3 2 1 has length $5$.

Therefore the answer is $7$.

Example 2

Input

8
7 5 3 1 3 5 7 9

Output

7

Explanation

The subsequence 7 5 3 1 3 5 7 decreases for three steps then increases for three steps, forming a balanced duck wave of length $7$.

Example 3

Input

7
1 2 10 20 15 3 0

Output

7

Explanation

The entire sequence forms a duck wave increasing until 20 and then decreasing afterwards, with total length 7.

Submit

The contest ended at 8:16 p.m. AEST on Thursday 2nd July. All submissions will be unofficial .