# Print the longest alternating subsequence

Given a sequence of numbers you have to print the longest alternating subsequence. A sequence is an alternating sequence when it will be maintaining like, *(increasing) -> ( decreasing ) -> (increasing ) -> (decreasing)* or *(decreasing) -> (increasing) -> (decreasing) -> (increasing)*.

Input:
T Test case
T no. of input array along with their element no. N
E.g.
3
8
2 3 4 8 2 5 6 8
8
2 3 4 8 2 6 5 4
7
6 5 9 2 10 77 5
Constrain:
1≤ T ≤ 20
1≤ N ≤50
1≤ A[i] ≤50
Output:
Print the longest alternating subsequence.

**Example**

T=3
Input:
8
2 3 4 8 2 5 6 8
Output:
4 8 2 5
Input:
8
2 3 4 8 2 6 5 4
Output:
4 8 2 6 4
Input:
7
6 5 9 2 10 77 5
Output:
6 5 9 2 10 5

Let

Nbe the number of elements say,X1, X2, X3, ..., XnLet

up(a)= the value at the index a of the increasing array, anddown(a)= the value at the index a of the decreasing array.To find out the length of the longest alternating sequence we will follow these steps,

up( index of current element)= down(index of the comparing element) + 1.down( index of current element)= up(index of the comparing element) + 1.To print the longest increasing odd-even subsequence, we will follow these steps,

C++ Implementation:

need an explanation for this answer? contact us directly to get an explanation for this answerOutput