Longest Subsequence with Difference of 2

Given an array of integers, find the longest contiguous subsequence such that for every consecutive pair of numbers in the subsequence, the difference is either 2 or -2. Formally, for a valid subsequence a₁, a₂, ..., a_k, for every i from 2 to k, it must satisfy:

\(a_i - a_{i-1} = 2 \quad \text{or} \quad a_i - a_{i-1} = -2\)

If more than one subsequence qualifies with the maximum length, output the first one encountered.

Note that the subsequence must be contiguous in the original array.

inputFormat

The first line contains an integer n which denotes the number of elements in the array. If n = 0, the array is empty. The second line (if n > 0) contains n space-separated integers representing the elements of the array.

outputFormat

Output the longest contiguous subsequence that satisfies the difference condition. The numbers should be printed in order separated by a single space. If the output subsequence has only one number, print that number. If the array is empty, output an empty line.

9
1 3 5 7 9 2 4 6 8

1 3 5 7 9