P16895 [GKS 2022 #G] Happy Subarrays

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$.

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$.