CF2111C.Equal Values

给定一个由 $n$ 个整数构成的数组 $a_1, a_2, \dots, a_n$。

每次操作，你可以执行以下两种操作之一：

• 选择一个位置 $i$（$1 < i \le n$），将第 $i$ 个元素左侧的所有元素都赋值为 $a_i$，即将所有 $a_j$（$1 \le j < i$）赋值为 $a_i$。该操作的代价为 $(i - 1) \cdot a_i$。
• 选择一个位置 $i$（$1 \le i < n$），将第 $i$ 个元素右侧的所有元素都赋值为 $a_i$，即将所有 $a_j$（$i < j \le n$）赋值为 $a_i$。该操作的代价为 $(n - i) \cdot a_i$。

注意，被操作影响到的元素即使已经等于 $a_i$，操作的代价也不会改变。

你可以进行任意次数的操作（包括零次）。请问将数组所有元素变为相等的最小总代价是多少？

第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。

每个测试用例的第一行包含一个整数 $n$（$2 \le n \le 5 \times 10^5$）。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le n$）。

所有测试用例中 $n$ 的总和不超过 $5 \times 10^5$。

对于每个测试用例，输出一个整数，表示将数组所有元素变为相等的最小总代价。

在第一个测试用例中，你可以进行两次操作：

• 选择 $i = 3$，将其左侧所有元素赋值为 $a_3$，代价为 $2 \times 1 = 2$；
• 选择 $i = 3$，将其右侧所有元素赋值为 $a_3$，代价为 $1 \times 1 = 1$。

总代价为 $2 + 1 = 3$。

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

由 ChatGPT 4.1 翻译