Longest Subarray with Limited Difference

You are given an array of integers. Your task is to find the length of the longest subarray (not necessarily contiguous in the original array) such that for any two elements \( a \) and \( b \) in that subarray, the absolute difference \( |a - b| \) is at most \( 1 \). In other words, all elements in the chosen subarray should be within \( 1 \) of each other.

Note: The subarray here is defined as a collection of elements from the original array, not necessarily contiguous, that maximizes the given condition when considering their frequency.

For example, given the array [1, 1, 2, 2, 4, 4, 5, 5, 5], one of the longest valid subarrays is [1, 1, 2, 2, 5] (by appropriate grouping of elements, the optimal answer here is 5). Your goal is to compute the maximum number of elements that can be chosen such that the difference between the smallest and largest values in the chosen set is at most 1.

inputFormat

The first line of input contains a single integer \( n \) denoting the number of elements in the array. The next line contains \( n \) space-separated integers representing the elements of the array.

If \( n = 0 \), the array is empty.

outputFormat

Output a single integer representing the length of the longest subarray where the difference between any two elements is at most \( 1 \).

9
1 1 2 2 4 4 5 5 5

5