题目描述

Let us define $F(B, L, R)$ as the sum of a subarray of an array $B$ bounded by indices $L$ and $R$ (both inclusive). Formally, $F(B, L, R) = B_L + B_{L+1} + \cdots + B_R$.

An array $C$ of length $K$ is called a happy array if all the prefix sums of $C$ are non-negative. Formally, the terms $F(C, 1, 1), F(C, 1, 2), \ldots, F(C, 1, K)$ are all non-negative.

Given an array $A$ of $N$ integers, find the result of adding the sums of all the happy subarrays in the array $A$.

输入格式

The first line of the input gives the number of test cases, $T$. $T$ test cases follow.

Each test case begins with one line consisting an integer $N$ denoting the number of integers in the input array $A$. Then the next line contains $N$ integers $A_1, A_2, \ldots, A_N$ representing the integers in given input array $A$.

输出格式

For each test case, output one line containing Case #$x$: $y$, where $x$ is the test case number (starting from $1$) and $y$ is the result of adding the sums of all happy subarrays in the given input array $A$.

2
5
1 -2 3 -2 4
3
1 0 3

Case #1: 14
Case #2: 12

提示

In Sample Case # $1$, the happy subarrays are [$1$], [$3$], [$3, -2$], [$3, -2, 4$], and [$4$] with their respective sums $1$, $3$, $1$, $5$, and $4$. After adding the sums obtained, the result is $14$.

In Sample Case # $2$, the happy subarrays are [$1$], [$1, 0$], [$1, 0, 3$], [$0$], [$0, 3$], and [$3$] with their respective sums $1$, $1$, $4$, $0$, $3$, and $3$. After adding the sums obtained, the result is $12$.

Limits

$1 \le T \le 100$.

$-800 \le A_i \le 800$, for all $i$.

Test Set 1

$1 \le N \le 200$.

Test Set 2

For at most $30$ cases:

$1 \le N \le 4 \times 10^5$.

For the remaining cases:

$1 \le N \le 200$.