Longest Subarray with Absolute Difference at Most 1

Given an array of n integers, find the length of the longest subarray (not necessarily contiguous) such that for any two elements \( x \) and \( y \) in the subarray, the absolute difference satisfies \( |x - y| \le 1 \). In other words, the subarray can only contain numbers that differ by at most 1.

For example:

• For the array [1, 1, 2, 2, 4, 4, 5, 5, 5], one optimal subarray is [1, 1, 2, 2, 5] (after pairing frequencies suitably) resulting in length 5.
• For the array [4, 6, 5, 3, 3, 1], an optimal selection can achieve length 3.

Your task is to implement a solution that reads the input from stdin and prints the result to stdout.

The core idea is to use the frequency counts of each number. For each distinct number \( k \), check the combined frequency of \( k \) and \( k-1 \) (i.e., \( frequency(k) + frequency(k-1) \)). The maximum such value is the answer.

Note: The answer for an empty array is 0.

inputFormat

The input is given via stdin in the following format:

n
a1 a2 ... an

where:

• n is the number of elements in the array.
• ai are the space-separated integers of the array.

outputFormat

Output a single integer representing the length of the longest subarray meeting the criteria to stdout.

## sample

9
1 1 2 2 4 4 5 5 5

5