CF1223F Stack Exterminable Arrays

让我们来看如下过程：最开始你有一个空栈和一个长度为 $l$ 的数组 $s$。你尝试按顺序将数组元素 $s_1, s_2, s_3, \dots, s_{l}$ 压入栈中。此外，如果栈为空，或者当前栈顶元素不等于当前元素，则你直接将当前元素压入栈顶。否则，你不仅不将当前元素压入栈，还要弹出栈顶元素。 如果这个过程结束后栈为空，则称数组 $s$ 是“可栈消灭”的。 以下是一些“可栈消灭”的数组示例： - $[1, 1]$； - $[2, 1, 1, 2]$； - $[1, 1, 2, 2]$； - $[1, 3, 3, 1, 2, 2]$； - $[3, 1, 3, 3, 1, 3]$； - $[3, 3, 3, 3, 3, 3]$； - $[5, 1, 2, 2, 1, 4, 4, 5]$； 以 $s = [5, 1, 2, 2, 1, 4, 4, 5]$ 为例，详细说明栈的变化过程（栈顶用加粗表示）： 1. 压入 $s_1 = 5$ 后，栈变为 $[\textbf{5}]$； 2. 压入 $s_2 = 1$ 后，栈变为 $[5, \textbf{1}]$； 3. 压入 $s_3 = 2$ 后，栈变为 $[5, 1, \textbf{2}]$； 4. 压入 $s_4 = 2$ 后，栈变为 $[5, \textbf{1}]$； 5. 压入 $s_5 = 1$ 后，栈变为 $[\textbf{5}]$； 6. 压入 $s_6 = 4$ 后，栈变为 $[5, \textbf{4}]$； 7. 压入 $s_7 = 4$ 后，栈变为 $[\textbf{5}]$； 8. 压入 $s_8 = 5$ 后，栈为空。 现在，给定一个数组 $a_1, a_2, \ldots, a_n$，你需要计算它有多少个子数组是“可栈消灭”的。 注意，你需要回答 $q$ 个独立的询问。

第一行包含一个整数 $q$（$1 \leq q \leq 3 \cdot 10^5$），表示询问的数量。 每个询问的第一行包含一个整数 $n$（$1 \leq n \leq 3 \cdot 10^5$），表示数组 $a$ 的长度。 每个询问的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \leq a_i \leq n$），表示数组的元素。 保证所有询问中 $n$ 的总和不超过 $3 \cdot 10^5$。

对于每个测试用例，输出一个整数，表示数组 $a$ 的“可栈消灭”子数组的数量，每行一个答案。

对于第一个询问，有四个“可栈消灭”子数组：$a_{1 \ldots 4} = [2, 1, 1, 2]$，$a_{2 \ldots 3} = [1, 1]$，$a_{2 \ldots 5} = [1, 1, 2, 2]$，$a_{4 \ldots 5} = [2, 2]$。 对于第二个询问，只有一个“可栈消灭”子数组，即 $a_{3 \ldots 4}$。 对于第三个询问，有八个“可栈消灭”子数组：$a_{1 \ldots 8}, a_{2 \ldots 5}, a_{2 \ldots 7}, a_{2 \ldots 9}, a_{3 \ldots 4}, a_{6 \ldots 7}, a_{6 \ldots 9}, a_{8 \ldots 9}$。 由 ChatGPT 4.1 翻译