← 返回题目列表

Codeforces · 1223/F

F. 堆栈可消除数组

中文机器翻译题面 查看原题

让我们看一下以下过程:最初有一个空堆栈和一个长度为 $$$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}$$$。