题目描述

定义 $F(B, L, R)$ 为数组 $B$ 中下标从 $L$ 到 $R$（包含两端）的子数组之和。形式化地，$F(B, L, R) = B_L + B_{L+1} + \dots + B_R$。

一个长度为 $K$ 的数组 $C$ 被称为 快乐数组，如果 $C$ 的所有前缀和均为非负。形式化地，项 $F(C, 1, 1), F(C, 1, 2), \dots, F(C, 1, K)$ 全部非负。

给定一个包含 $N$ 个整数的数组 $A$，求 $A$ 中所有快乐子数组的和的总和。

输入格式

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。

每个测试用例的第一行包含一个整数 $N$，表示输入数组 $A$ 中整数的个数。第二行包含 $N$ 个整数 $A_1, A_2, \dots, A_N$，表示给定的输入数组 $A$。

输出格式

对于每个测试用例，输出一行，格式为 Case #x: y，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是给定输入数组 $A$ 中所有快乐子数组的和的总和。

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

Case #1: 14
Case #2: 12

提示

在样例 #1 中，快乐子数组为 $[1]$、$[3]$、$[3, -2]$、$[3, -2, 4]$ 和 $[4]$，它们的和分别为 $1$、$3$、$1$、$5$ 和 $4$。将这些和相加得到 $14$。

在样例 #2 中，快乐子数组为 $[1]$、$[1, 0]$、$[1, 0, 3]$、$[0]$、$[0, 3]$ 和 $[3]$，它们的和分别为 $1$、$1$、$4$、$0$、$3$ 和 $3$。将这些和相加得到 $12$。

限制条件

$1 \le T \le 100$。

对于所有 $i$，$-800 \le A_i \le 800$。

测试集 1

$1 \le N \le 200$。

测试集 2

最多 $30$ 个测试用例满足：

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

其余测试用例满足：

$1 \le N \le 200$。

翻译由 DeepSeek V4 Pro 完成