Bai Hao Wanna Have A Girl Friend

Time Limit: 1000 ms Memory Limit: 65536 KiB

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

Source

【第八届山东理工大学ACM网络编程擂台赛 正式赛】Q^Q & QAQ