← 返回题目列表

Codeforces · 2111/C

C. 等值

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

给定一个数组 $$$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$$$。

输出

对于每个测试用例,打印一个整数 - 使数组的所有元素相等的最小总操作成本。

示例

输入
复制

3
4
2 4 1 3
3
1 1 1
10
7 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$$$。

在第二个测试用例中,所有元素已经相等,因此不需要执行任何操作。