Sequence

Interview

Time limit1sMemory limit128 MB

Summary

Find the maximum length of a contiguous subarray of digits that is either nondecreasing or nonincreasing.

Level: Easy3 of 10
Topics: Array, Dynamic programming, Implementation
Solved: No attempts yet

Problem

You are given a sequence of length N made of digits from 0 to 9. Consider contiguous segments that, from left to right, are either nondecreasing or nonincreasing.

Print the maximum possible length of such a segment. Equal adjacent digits satisfy both direction conditions.

Input

The first line contains the length N of the sequence.

The second line contains N digits separated by spaces.

N is an integer between 1 and 100,000, inclusive.

Output

Print the length of the longest contiguous segment that is nondecreasing or nonincreasing.

Examples3

Example 1
Input
```
9
1 2 2 4 4 5 7 7 2
```
Expected output
```
8
```
Example 2
Input
```
9
4 1 3 3 2 2 9 2 3
```
Expected output
```
4
```
Example 3
Input
```
11
1 5 3 6 4 7 1 3 2 9 5
```
Expected output
```
2
```