的 距离 ,表示为 $$$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$$$。
输出
对于每个测试用例,输出一个整数,表示所有漂亮数组中最大可能的美感。
示例
输入复制
441 2 1 222 2101 2 1 5 1 2 2 1 1 281 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$$$。