← 返回题目列表

Codeforces · 1527/C

C. 序列对权重

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

序列的权重定义为具有相同值 ($$$a_{i} = a_{j}$$$) 的无序索引对 $$$(i,j)$$$ (此处 $$$i \lt j$$$)的数量。例如,序列 $$$a = [1, 1, 2, 2, 1]$$$ 的权重为 $$$4$$$。具有相同值的无序索引对的集合是 $$$(1, 2)$$$、$$$(1, 5)$$$、$$$(2, 5)$$$ 和 $$$(3, 4)$$$。

给定一个由 $$$n$$$ 整数组成的序列 $$$a$$$。打印 $$$a$$$ 所有子段的权重总和。

序列 $$$b$$$ 是序列 $$$a$$$ 的子段,如果 $$$b$$$ 可以通过从 $$$a$$$ 删除开头的几个(可能是零个或全部)元素和从末尾删除几个(可能是零个或全部)元素来获得。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^5$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^5$$$)。

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

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

输出

对于每个测试用例,打印一个整数 - $$$a$$$ 的所有子段的权重之和。

示例

输入 #1

2
4
1 2 1 1
4
1 2 3 4

输出 #1

6
0

注意

- 在测试用例 $$$1$$$ 中,序列 $$$[1, 2, 1, 1]$$$ 大小大于 $$$1$$$ 的所有可能子段是: $$$[1, 2]$$$ 具有 $$$0$$$ 有效无序对; $$$[2, 1]$$$ 具有 $$$0$$$ 有效无序对; $$$[1, 1]$$$ 具有 $$$1$$$ 有效无序对; $$$[1, 2, 1]$$$ 具有 $$$1$$$ 有效无序对; $$$[2, 1, 1]$$$ 具有 $$$1$$$ 有效无序对; $$$[1, 2, 1, 1]$$$ 具有 $$$3$$$ 有效无序对。 答案是$$$6$$$。
- 在测试用例 $$$2$$$ 中,序列的所有元素都是不同的。因此,任何子数组都不存在具有相同值的有效无序对。答案是$$$0$$$。