You are given an array ‘ARR’ of integers. Your task is to find the length of the longest alternating subsequence.
Note:
A sequence a1, a2, .... an is called an alternating sequence if its elements satisfy one of the following relations : a1 < a2 > a3 < a4 > a5..... or a1 > a2 < a3 > a4 < a5.
For example:
'ARR' = {3, 10, 1, 2, 30}, the longest alternating subsequence for this array can be {3, 10, 1, 30} or {3, 10, 2, 30}. Therefore, the answer will be 4.
The first line of input contains an integer 'T' denoting the number of test cases.
The first line of each test case contains a single integer 'N' representing the length of the array.
The second line of each test case contains 'N' space-separated integers representing the elements of the array 'ARR'.
For each test case, return a single integer which is the length of the longest alternating subsequence.
Print the output of each test case in a separate line.
Note:
You don’t have to print anything; it has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 5
1 <= N <= 5000
1 <= ARR[i] <= 10^5
Where 'ARR[i]' denotes the ith element of 'ARR'.
Time limit: 1 sec
Sample Input 1 :
2
7
1 2 5 3 10 15 12
4
1 4 2 3
Sample Output 1 :
5
4
Explanation of Sample Output 1:
In test case 1, Given 'ARR' = {1,2,5,3,10,15,12}, we can see that the longest alternating subsequence for this array can be {1,5,3,15,12} or {2,5,3,15,12}. Therefore, the length will be 5.
In test case 2, Given 'ARR' = {1,4,2,3} we can see that the longest alternating subsequence for this array will be {1,4,2,3}. Therefore, length will be 4.
Sample Input 2 :
2
5
1 2 3 4 5
3
1 3 2
Sample Output 2 :
2
3
Explanation of Sample Output 2:
In test case 1, Given 'ARR' = {1,2,3,4,5}, we can see that the longest alternating subsequence for this array can be any pair of two elements. Therefore, the length will be 2.
In test case 2, Given 'ARR' = {1,3,2} we can see that the longest alternating subsequence for this array will be {1,3,2}. Therefore, the length will be 3.