题目描述

对于一个 01 序列 $\{b_i\}$，我们称它是 好的 当且仅当可以通过若干次下面的操作变成一个全 $1$ 序列：

• 选择一个子段 $[b_l,b_{l+1},\ldots,b_r]$。
• 如果这个子段中 $1$ 的出现次数严格多于 $0$ 的出现次数，那么将整个子段的元素全部修改为 $1$。

给定一个长为 $n$ 的 01 序列 $\{a_i\}$，求有多少个区间 $[l,r]$ 使得子段 $[a_l,\ldots,a_r]$ 是 好的。

输入格式

第一行一个正整数 $T$，代表数据组数。接下来 $T$ 组数据，每组数据的格式如下：

• 第一行一个正整数 $n$，代表序列长度；
• 接下来一行 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

输出格式

对于每组数据，输出一个整数，代表 $\{a_i\}$ 中好的子段个数。

3
3
1 0 1
3
1 1 1
4
0 1 0 0

3
6
1

数据范围

• 对于 $30\%$ 的数据，$n \le 5$；
• 对于 $60\%$ 的数据，$n \le 20$；
• 对于 $100\%$ 的数据，$1 \le T \le 10^4$，$1 \le n,\sum n \le 2 \cdot 10^5$，$0 \le a_i \le 1$。