Election in Sylhet City

Sylhet is a very beautiful city in northeastern Bangladesh. Sylhet is one of the most important spiritual and cultural centers of Bangladesh.

There are $N$ people in this city. They live in their houses. Houses in this city are arranged linearly in a consecutive manner, having house identification number starting from 1. Exactly one person lives in a house.

This time all people in this city are busy for the election of the mayor in the city. Recently, the rule for the election of the mayor has been reformed. Previously, the mayor of the city was elected based upon the age. The mayor is used to be a person who is older than all the others in the city. If more than one people were eligible, then the person with the lowest house number was finally elected for the mayor position.

According to the recent rule, there will be exactly two mayors in the city. Any two people can form a pairing and apply for the position of mayor if the summation of their ages is strictly greater than the age of any people who belongs on the way in between their houses (including their own ages).

Later on, the winning pair for the mayor position will be determined based on the individual voting from all $N$ peoples.

Now, your task is to figure out that out of all possible pairings among two people i.e. $\frac{N(N-1)}{2}$, how many pairings will be valid so that they can apply for the mayor position?

Input

Input starts with an integer $T$ ($1≤T≤5$) denoting the total number of test-cases. Every test-case starts with $N$ ($1 ≤ N ≤ 200000$), denoting the total number of people who live in Sylhet city. This is followed by a single line containing $N$ non-negative integer numbers having value at most $10^9$, separated by a single space, denoting their ages.

Output

For every case of input, output an integer number in a single line denoting the answer as described in the problem statement.

Sample

Input	Output
1 5 1 3 2 5 4	8
Valid pairs of people with house IDs are: $(1,2)$, $(1,4)$, $(2,3)$, $(2,4)$, $(2,5)$, $(3,4)$, $(3,5)$, $(4,5)$.