Longest Zigzag Subsequence

Given an array of integers, find the longest subsequence which forms a zigzag sequence. A sequence is considered to be zigzag if the differences between consecutive elements strictly alternate in sign. In other words, if the sequence is a₁, a₂, ..., a_k, then for all valid i (1 ≤ i < k-1), the following must hold:

$$ (a_{i+1} - a_i) \times (a_{i+2} - a_{i+1}) < 0 $$

If the array contains only one element, then the longest zigzag subsequence is the array itself. In cases where multiple answers exist, any valid answer is accepted.

inputFormat

The input is given via standard input (stdin) and consists of two lines. The first line contains an integer N (1 ≤ N ≤ 10⁵) representing the number of elements. The second line contains N space-separated integers.

outputFormat

Print the result to standard output (stdout) using two lines. The first line should contain the length of the longest zigzag subsequence. The second line should contain the subsequence itself, with the numbers separated by a single space.

## sample

6
1 7 4 9 2 5

6
1 7 4 9 2 5

</p>