← 返回题目列表

Codeforces · 1883/F

F. 你真漂亮

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

给定一个整数数组 $$$a_1, a_2, \ldots, a_n$$$。计算该数组 $$$1 \leq l \leq r \leq n$$$ 的子数组数量,使得:

- 数组 $$$b = [a_l, a_{l+1}, \ldots, a_r]$$$ 作为子序列在数组 $$$a$$$ 中只出现一次。换句话说,只有一种方法可以选择一组索引 $$$1 \leq i_1 < i_2 < \ldots < i_{r - l + 1} \leq n$$$,使得 $$$b_j = a_{i_j}$$$ 对于所有 $$$1 \leq j \leq r - l + 1$$$。

输入

每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。接下来是他们的描述。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 10^5$$$) — 数组 $$$a$$$ 的大小。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$)。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,输出合适子数组的数量。

示例

输入 #1

6
1
1
2
1 1
3
1 2 1
4
2 3 2 1
5
4 5 4 5 4
10
1 7 7 2 3 4 3 2 1 100

输出 #1

1
1
4
7
4
28

注意

在第一个测试用例中,只有一个子数组 $$$(1, 1)$$$ 适合我们。

在第二个测试用例中,只有一个子数组 $$$(1, 2)$$$ 适合我们。子数组 $$$(1, 1)$$$ 和 $$$(2, 2)$$$ 不适合我们,因为子序列 $$$[1]$$$ 在数组中出现了两次。

在第三个测试用例中,除了 $$$(1, 1)$$$ 和 $$$(3, 3)$$$ 之外的所有子数组都是合适的。