Longest Subsequence with Close Values

Given an array of integers, find the length of the longest subsequence (not necessarily contiguous) such that the difference between the maximum and minimum values in the subsequence is at most 1. In other words, any two numbers in the chosen subsequence differ by no more than 1.

For example, consider the array [1, 2, 2, 3, 1, 2]. The longest valid subsequence is [1, 2, 2, 1, 2] which has a length of 5.

The subsequence does not need to preserve the order from the original array (i.e. it is not required to be contiguous). You may assume the array only contains integers.

inputFormat

The input is given in two parts via standard input. The first line contains a non-negative integer n representing the number of elements in the array. The second line contains n space-separated integers. If n is 0, the second line may be omitted.

outputFormat

Output a single integer to the standard output: the length of the longest subsequence where the difference between its maximum and minimum elements is at most 1.

6
1 2 2 3 1 2

5