Longest Consecutive Difference Subsequence

You are given an array of integers. A subsequence of this array is a sequence that can be derived by deleting some or no elements without changing the order of the remaining elements. Your task is to find the length of the longest subsequence such that the absolute difference between every pair of consecutive elements is (1). In other words, for a subsequence (a_1, a_2, \ldots, a_k), it must hold that (|a_{i+1} - a_i| = 1) for all (1 \le i < k).

inputFormat

The first line contains an integer (n), representing the number of elements in the array. The second line contains (n) space-separated integers.

outputFormat

Output a single integer, the length of the longest subsequence where the absolute difference between consecutive elements is (1).## sample

6
1 2 3 4 5 6

6