给定一个数组 $$$a_1, a_2, \dots, a_n$$$,由 $$$n$$$ 整数组成。
在一次操作中,您可以执行以下操作之一:
- 选择一个位置 $$$i$$$ ($$$1 \lt i \le n$$$) 并使 $$$i$$$ 左边的所有元素等于 $$$a_i$$$。也就是说,将值 $$$a_i$$$ 分配给所有 $$$a_j$$$ ($$$1 \le j \lt i$$$)。这种操作的成本是$$$(i - 1) \cdot a_i$$$。
- 选择位置 $$$i$$$ ($$$1 \le i \lt n$$$) 并使 $$$i$$$ 右侧的所有元素等于 $$$a_i$$$。也就是说,将值 $$$a_i$$$ 分配给所有 $$$a_j$$$ ($$$i \lt j \le n$$$)。这种操作的成本是$$$(n - i) \cdot a_i$$$。
请注意,受操作影响的元素可能已经等于 $$$a_i$$$,但这不会改变成本。
您可以执行任意数量的操作(包括零次)。使数组中所有元素相等的最小总成本是多少?
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 5 \cdot 10^5$$$)。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$)。
所有测试用例的 $$$n$$$ 总和不超过 $$$5 \cdot 10^5$$$。
输出
对于每个测试用例,打印一个整数 - 使数组的所有元素相等的最小总操作成本。
示例
输入复制
342 4 1 331 1 1107 5 5 5 10 9 9 4 6 10
输出复制
3 0 35
注意
在第一个测试用例中,您可以执行两次操作:
- 选择 $$$i = 3$$$ 并使其左边的所有元素都等于它,成本将为 $$$2 \cdot 1 = 2$$$;
- 选择 $$$i = 3$$$ 并使其右侧的所有元素都等于它,成本将为 $$$1 \cdot 1 = 1$$$。
总成本为 $$$2 + 1 = 3$$$。
在第二个测试用例中,所有元素已经相等,因此不需要执行任何操作。