Longest Consecutive Difference Subsequence

Given an array of n integers, find the length of the longest subsequence such that the absolute difference between any two consecutive elements is exactly \(1\). A subsequence is a sequence that can be derived from the array by deleting some elements without changing the order of the remaining elements.

Note: The difference between two consecutive elements \(a\) and \(b\) in the subsequence must satisfy \(|a - b| = 1\).

For example, if the array is [10, 9, 4, 5, 4, 8, 6], one possible subsequence with the required property is [10, 9, 8] and its length is 3.

inputFormat

The input is given via standard input (stdin) and consists of two lines:

• The first line contains a single integer n, the number of elements in the array.
• The second line contains n space-separated integers.

You may assume that n is at least 1.

outputFormat

Output a single integer to standard output (stdout) which is the length of the longest subsequence where any two consecutive numbers have an absolute difference of exactly 1.

7
10 9 4 5 4 8 6

3