Build It on a Foundation Stone

Interview

Time limit1sMemory limit512 MB

Summary

Find the longest contiguous subarray whose maximum minus minimum is at most 2, given values from 1 to 10.

Level: Medium5 of 10
Topics: Sliding window, Two pointers, Array, Implementation
Solved: No attempts yet

Problem

Standing tall on the high Namsan

(omitted)

Build it on a foundation stone

The ground of Seonrin

Foundation stone: a wide, flat, large rock, a bedrock boulder

A sequence is a foundation stone when the difference between its maximum and minimum values is at most 2.

For example, 1 2 3 3 1 2 is a foundation stone because the difference between its maximum (3) and minimum (1) is 2, while 2 6 5 4 is not, because the difference between its maximum (6) and minimum (2) is 4.

Given a sequence, write a program that finds the length of the longest foundation stone among its contiguous subsequences (substrings).

Input

The first line gives the length of the sequence, $N$ .

The second line gives the elements of the sequence $A$ , namely $A_1, A_2, \cdots, A_N$ , separated by spaces.

Output

Print the length of the longest foundation stone among the contiguous subsequences of $A$ .

Constraints

$1 \leq N \leq 1\,000\,000$

$1 \leq A_i \leq 10$

Examples2

Example 1
Input
```
5
1 2 1 3 1
```
Expected output
```
5
```
Example 2
Input
```
7
1 2 3 4 2 5 7
```
Expected output
```
4
```