许多许多头 2 - 题目

多头杯（Multi-Heads Cup，简称 MHC）是一项为拥有很多很多脑袋的参赛者举办的全球性程序设计竞赛。在 2023 年，该赛事的总裁判小蓝鱼（Little Cyan Fish）利用多种类型的括号解决了一个棘手的身份验证问题。

那是小蓝鱼第一次见到拥有很多很多脑袋的参赛者。而这一次，小蓝鱼给拥有很多很多脑袋的好朋友带来了另一个括号问题。小蓝鱼手里有 $n$ 种类型的括号，每种类型的括号都分为左括号和右括号。为了方便起见，我们用 $L^i$ 表示第 $i$ 种类型的左括号，用 $R^i$ 表示第 $i$ 种类型的右括号。

“嘿，别忘了，”小蓝鱼想，“我以前向你介绍过什么是合法括号序列！”为了确保你理解合法括号序列的概念，小蓝鱼准备了以下关于合法括号序列的正式定义：

例如，“()”、“()()” 和 “(())” 是合法括号序列，但 “)(”、“(” 和 “))” 不是。

现在，小蓝鱼给你一个长度为 $n$ 的括号序列 $S$，其中包含 $n$ 种类型的括号。不幸的是，小蓝鱼忘记了某些位置的括号类型，也忘记了这些位置的括号方向。对这些位置的记忆已经变得模糊，被小蓝鱼用 ? 表示。

小蓝鱼非常好奇，对于所有 $1 \le l \le r \le n$，有多少个对 $(l, r)$ 对应的子串 $S[l \dots r]$，满足存在一种用某种方向的某种类型括号填补 ? 的方案，使得对于每个 $1 \le i \le n$，均满足：

例如，如果我们用 “()” 表示第一种括号，用 “[]” 表示第二种括号，那么括号字符串 ([?) 满足上述条件，因为我们可以将 ? 替换为 ]。(?)] 也满足上述条件，因为我们可以将 ? 替换为 [。

小蓝鱼想要你计算所有合法对 $(l, r)$ 的数量。

输入包含多组测试数据。输入的第一行包含一个整数 $T$ ($1 \le T$)，表示测试数据的组数。

对于每组测试数据：第一行包含一个整数 $n$ ($1 \le n \le 2 \times 10^5$)，表示括号字符串的长度。

下一行包含 $n$ 个整数 $x_1, x_2, \dots, x_n$ ($-n \le x_i \le n$)。这 $n$ 个整数描述了括号字符串的信息，其中：

保证所有测试数据的 $n$ 之和不超过 $2 \times 10^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

QOJ.ac