#P17968. Many Many Heads 2

Many Many Heads 2

Many Many Heads 2

有 nn 种括号,第 ii 种左、右括号分别记为 Li,RiL_i,R_i。一个只含一种括号的序列称为平衡括号序列,当且仅当它可由下列规则生成:

  • 空串是平衡括号序列;
  • 若 AA 平衡,则 (A)(A) 平衡;
  • 若 A,BA,B 都平衡,则 ABAB 平衡。

给定长度为 nn 的序列 xx。若 xi>0x_i>0,该位置为 LxiL_{x_i};若 xi<0x_i<0,该位置为 R−xiR_{-x_i};若 xi=0x_i=0,该位置是未知括号,可独立填成任意一种左括号或右括号。

求有多少对 (l,r)(l,r),1≤l≤r≤n1\le l\le r\le n,使区间 [l,r][l,r] 内的未知位置存在一种填法,满足:对每一种括号,单独提取该种括号后,得到的序列都是平衡括号序列。

不同种类的括号允许交叉。例如 L1,L2,R1,R2L_1,L_2,R_1,R_2 满足条件。每个区间独立选择填法,不同填法不重复计数。

输入格式

第一行是测试用例数 T≥1T\ge1。每组数据第一行是 nn,第二行是 nn 个整数 x1,…,xnx_1,\ldots,x_n。

1≤n≤2×1051\le n\le2\times10^5,−n≤xi≤n-n\le x_i\le n。所有测试用例的 nn 之和不超过 2×1052\times10^5。

输出格式

每组数据输出一行一个整数,表示合法区间的数量。

样例输入

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