Longest Subsequence with Limited Difference

Given an array of positive integers, your task is to find the length of the longest subsequence such that the absolute difference between any two elements is at most 1. In other words, the subsequence can only contain numbers that are equal or consecutive.

The condition can be formally expressed as: \( |a - b| \le 1 \) for every pair \(a, b\) in the subsequence.

For example, in the array [1, 2, 2, 3, 1, 2], the longest valid subsequence is [1, 2, 2, 1, 2] with a length of 5.

inputFormat

The first line contains an integer \(n\), the number of elements in the array.

The second line contains \(n\) space-separated positive integers.

outputFormat

Output a single integer denoting the length of the longest subsequence that satisfies the condition where the absolute difference between any two elements is at most 1.

6
1 2 2 3 1 2

5