C. A Noteworthy Debut
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
Guitar, Loneliness and Blue Planet
Kessoku Band, Kessoku Band

After many years of songwriting and practicing, the up-and-coming UTBC (UT Beats Club) is finally ready to debut! In order to do so, they must choose some of their songs to record for their debut album.

Currently, they have written a total of $$$n$$$ songs, each with their own excitement level. The list of songs can be represented by an array $$$a$$$, where the $$$i$$$-th song in the array has an excitement level of $$$a_i$$$. In order for their album to be thematically coherent, UTBC has decided they want to choose a subarray$$$^†$$$ of songs from $$$a$$$ to put on the album.

UTBC doesn't want their debut to be a flop, so they want to choose which songs they put on their record album carefully. After extensive market research, they have discovered that audiences love an album that contains a song that stands out. In particular, a record album is considered noteworthy if it contains a song whose excitement level is strictly greater than the sum of the excitement levels of all the other songs on the album. For example, [3, 1, 1] is noteworthy because $$$3 \gt 1+1$$$, whereas [2, 2] and [1, 2, 3] are not.

Now UTBC wants to know, given the array $$$a$$$ of their songs, how many different possible noteworthy record albums could they produce as their debut album? Help them calculate this answer before they debut!

$$$^†$$$A subarray of $$$a$$$ is defined as a sequence of consecutive elements of $$$a$$$, i.e. the array $$$a_i,a_{i+1},\dots,a_j$$$ for some $$$1\leq i\leq j\leq n$$$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ $$$(1\leq t\leq10^4)$$$. The description of the test cases follows.

The first line of each test case contains an integer $$$n$$$ $$$(1\leq n\leq 2\cdot 10^5)$$$ — the number of songs written by UTBC.

The second line of each test case contains $$$n$$$ integers $$$a_1,a_2,\dots,a_n$$$ $$$(1\leq a_i\leq10^9)$$$ — the excitement levels of the songs in the array.

It is guaranteed that the sum of the values of $$$n$$$ for all test cases does not exceed $$$2\cdot10^5$$$.

Output

For each test case output one integer — the number of different subarrays of songs that will produce a noteworthy record album.

Example
Input
5
1
1
2
1 2
3
3 1 1
4
1 5 2 1
5
1 3 5 10 12
Output
1
3
5
10
12
Note

For the first test case, the only noteworthy subarray is [1].

For the second test case, the noteworthy subarrays are [1], [2], [1, 2].

For the third test case, the noteworthy subarrays are [3], [1], [1], [3, 1], [3, 1, 1].