让我们看一下以下过程:最初有一个空堆栈和一个长度为 $$$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 \le q \le 3 \cdot 10^5$$$) — 查询数。
每个查询的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$) — 数组 $$$a$$$ 的长度。
每个查询的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$) - 元素。
保证所有查询的所有 $$$n$$$ 之和不超过 $$$3 \cdot 10^5$$$。
输出
对于每个测试用例,在一行中打印一个整数 - 数组 $$$a$$$ 的堆栈可终止子数组的数量。
示例
输入 #1
3 5 2 1 1 2 2 6 1 2 1 1 3 2 9 3 1 2 2 1 6 6 3 3
输出 #1
4 1 8
注意
在第一个查询中有四个堆栈可消除子数组: $$$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}$$$。