Longest Subsequence with Difference One

Given a sequence of n integers, find the length of the longest subsequence (not necessarily contiguous) such that the absolute difference between every two consecutive elements is exactly 1.

The subsequence must follow the original order of elements, but elements can be skipped. Formally, if the subsequence is \(a_{i_1}, a_{i_2}, \dots, a_{i_k}\) with \(1 \le i_1 < i_2 < \dots < i_k \le n\), then for all \(1 \leq j < k\), it must hold that \(|a_{i_{j+1}} - a_{i_j}| = 1\).

Your task is to compute and output the length of this longest valid subsequence.

inputFormat

The first line of input contains an integer n indicating the number of elements in the sequence. The second line contains n space-separated integers representing the sequence.

If n = 0, the sequence is empty.

outputFormat

Output a single integer which is the length of the longest subsequence where the absolute difference between any two consecutive elements is 1.

6
1 2 2 3 3 4

4