#P17968. Many Many Heads 2
Many Many Heads 2
Many Many Heads 2
有 种括号,第 种左、右括号分别记为 。一个只含一种括号的序列称为平衡括号序列,当且仅当它可由下列规则生成:
- 空串是平衡括号序列;
- 若 平衡,则 平衡;
- 若 都平衡,则 平衡。
给定长度为 的序列 。若 ,该位置为 ;若 ,该位置为 ;若 ,该位置是未知括号,可独立填成任意一种左括号或右括号。
求有多少对 ,,使区间 内的未知位置存在一种填法,满足:对每一种括号,单独提取该种括号后,得到的序列都是平衡括号序列。
不同种类的括号允许交叉。例如 满足条件。每个区间独立选择填法,不同填法不重复计数。
输入格式
第一行是测试用例数 。每组数据第一行是 ,第二行是 个整数 。
,。所有测试用例的 之和不超过 。
输出格式
每组数据输出一行一个整数,表示合法区间的数量。
样例输入
4
4
1 2 -1 -2
4
1 0 -2 0
6
1 2 3 -3 -2 -1
8
1 0 0 3 0 0 0 -2
样例输出
1
3
3
14