题目描述

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

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

1. 向左覆盖：选择一个位置 $i$（$1<i≤n$），并将 $i$ 左侧的所有元素的值设为 $a_i$。即，对所有 $a_j$（$1≤j<i$）赋值为 $a_i$。该操作的成本为 $(i−1)⋅a_i$。
2. 向右覆盖：选择一个位置 $i$（$1≤i<n$），并将 $i$ 右侧的所有元素的值设为 $a_i$。即，对所有 $a_j$（$i<j≤n$）赋值为 $a_i$。该操作的成本为 $(n−i)⋅a_i$。

注意：

• 受操作影响的元素可能已经等于 $a_i$，但这不会改变操作的成本。
• 你可以执行任意次数的操作（包括零次）。

目标： 找到使数组中所有元素相等的最小总操作成本。

输入格式

第一行包含一个整数 $t$（$1≤t≤10^4$）——测试用例的数量。

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

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

所有测试用例的 $n$ 之和不超过 $5\times10^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

样例1解释

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

1. 选择 $i=3$，并将其左侧的所有元素设为 $a_3=1$，成本为 $(3−1)\times1=2$；
2. 选择 $i=3$，并将其右侧的所有元素设为 $a_3=1$，成本为 $(4−3)\times1=1$。

总成本为 $2+1=3$。

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