Bai Hao Wanna Have A Girl Friend
Problem Description
Winter is coming, and Bai Hao feels so cold. He wanna have a girl friend to warm his hand, so he asks master UMR to help him hold a beauty contest.
Now there're n candidates standing in one line. But Bai Hao doesn't like a sequence with different heights.
In order to satisfy Bai Hao, UMR decides to choose some of them to form a new sequence which their height is neither ascending nor descending.
UMR wants to know the number of possible schemes.
Note: If two girls with same height stand in different position, we consider them as only one scheme.
Input
The first line of input contains an integer T (0 < T < 100), indicating the number of test cases.
For each case:
- The first line contains an integer n, denoting there're n candidates (1 <= n < 10^5)
- Next line contains n integers separated by spaces, denoting the height of each candidate hi (1 <= hi <= 10^5)
Output
For each case, output an integer in one line, indicating the number of schemes.
The value of each output will not exceed the range of int.
Sample Input
3 4 160 170 170 170 5 165 170 175 175 170 3 100 100 100
Sample Output
8 7 7
Hint
For the first sample input, UMR has 8 schemes (represented as the position of each candidate in original sequence):
1
2
3
4
2 3
2 4
3 4
2 3 4