← 返回题目列表

Codeforces · 2101/C

C. 23王国

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

的 距离 ,表示为 $$$d_x(c)$$$,定义为 $$$c$$$ 中任意两次出现 $$$x$$$ 之间的最大差距。

形式上,$$$d_x(c) = \max(j - i)$$$ 在所有 $$$i \lt j$$$ 上,其中 $$$c_i = c_j = x$$$。如果 $$$x$$$ 在 $$$c$$$ 中只出现一次或根本不出现,则 $$$d_x(c) = 0$$$。 数组的

的 美女 是数组中每个不同值的距离之和。形式上,数组 $$$c$$$ 的美度等于 $$$\sum\limits_{1\le x\le n} d_x(c)$$$。

给定一个长度为 $$$n$$$ 的数组 $$$a$$$,数组 $$$b$$$ 为 不错 如果它的长度也为 $$$n$$$ 并且其元素对于所有 $$$1\le i\le n$$$ 满足 $$$1\le b_i\le a_i$$$。你的任务是找到任何漂亮阵列的最大可能的美感。

输入

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

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1\le n\le 2\cdot10^5$$$) — 数组 $$$a$$$ 的长度。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1,a_2,\ldots,a_n$$$ ($$$1\le a_i\le n$$$) — 数组 $$$a$$$ 的元素。

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

输出

对于每个测试用例,输出一个整数,表示所有漂亮数组中最大可能的美感。

示例

输入
复制

4
4
1 2 1 2
2
2 2
10
1 2 1 5 1 2 2 1 1 2
8
1 5 2 8 4 1 4 2

输出
复制

4
1
16
16

注意

在第一个测试用例中,如果 $$$b = [1, 2, 1, 2]$$$,则 $$$d_1(b) = 3 - 1 = 2$$$ 和 $$$d_2(b) = 4 - 2 = 2$$$,结果为 $$$2 + 2 = 4$$$。可以证明,不存在美感大于$$$4$$$的漂亮数组。

在第二个测试用例中, $$$b = [1, 1]$$$ 和 $$$b = [2, 2]$$$ 都是有效的解决方案,其美观度为 $$$1$$$。

在第三个测试用例中,如果 $$$b = [1, 2, 1, 4, 1, 2, 1, 1, 1, 2]$$$ 且 $$$d_1(b) = 9 - 1 = 8$$$、$$$d_2(b) = 10 - 2 = 8$$$ 和 $$$d_4(b) = 0$$$,导致美丽$$$16$$$。