You are given an array of n elements you allowed to delete at max one element from provided array. The order of elements remain the same .you are required to maximize the number of subarrays that contain both maximum and minimum element of the resultant array . A subarrays is the sequence of consecutive element of the array

Input

T no of test case

N size of array

N array element

Output

For each test case print one single integer the maximum number of subarrays that contains both maximum and minimum elements of the resultant array

Examples

4

6

7 2 5 4 3 1

7

1 2 3 4 5 6 7

6

2 5 3 2 5 5

4

5 5 5 5

Output

4

1

12

15

Test case 1 explanation

If we delete 1 from the array then the resultant array will be 7 2 5 4 3

So the number of subarrays will contains max 7 and minimum 2 will be 4

[7,2]

[7,2,5]

[7,2,5,4]

[7,2,5,4,3]

I think we can use this logic first point out the first minimum and second minimum ans also the first maximum and second maximum.count the number of subarrays that include (firstmax,firstmin),(firstmax,secondmin),(secondmax,firstmin) return max answer among these.I think this works

how are we handling the cases where there are equal elements in this.

Can you help me with the logic for those ones, I couldnâ€™t solve both of them

Can you give an example

Letâ€™s first write a function to compute the no. of such subarrays if the array is fixed (there are no deletions). Letâ€™s say maximum element(s) is/are max and minimum element(s) is/are min. Now the main problem is handling with multiple instances of maximum and minimum elements. We can use dp to handle this. Say **dp[i] is no.of subarrays of array until index i such that the subarray consists of both max and min**. Now writing a recursive relation should be easy once you know the indices of previous instance of minimum and previous instance of maximum. So, we can compute this function in O(n).

Now letâ€™s handle deletion case. U might have already realized that you can delete either maximum element or minimum element. **If both no.of instances of maximum and no.of instances of minimum are greater than 1, then deletion of any element would only result in decreasing the no.of subarrays consisting min and max (think about it). Hence, we donâ€™t perform deletion in this case.** Now, if no.of instances of maximum element = 1, then we delete that element and compute the function for the new array. Same, is the case if no.of instances of minimum element = 1. Finally, find the maximum out of all.