题目描述

在未来的太空探险队中，AI 机器人「织星者」负责管理一个星际导航站。

导航站的星图显示器上显示了一串重要的星标数字 $a_1,\ a_2,\ …,\ a_n$，它们代表了不同星际坐标点的能量等级。为了让星图更加协调稳定，织星者需要将所有的星标数字调整为相同值。

每次操作都需要消耗星能，具体方式如下：

• 向左同调：选择一个位置 $i$ ($2≤i≤n$)，将位置 $1$ 到 $i−1$ 的所有数字都变为 $a_i$，消耗星能 $(i−1)×a_i$

• 向右同调：选择一个位置 $i\ (1≤i<n)$，将位置 $i+1$ 到 $n$ 的所有数字都变为 $a_i$，消耗星能 $(n−i)×a_i$

注意：即使目标位置的数字已经等于 $a_i$，操作仍然会消耗对应的星能。

织星者希望以最少的总星能消耗完成这次星图校准。你能为它计算出这个最小值吗？

输入格式

第一行一个整数 $t\ (1≤t≤10^4)$，表示测试数据组数。

接下来 $t$ 组数据，每组包含：

• 第一行一个整数 $n\ (2≤n≤5×10^5)$，表示星标数字的数量。
• 第二行 $n$ 个整数 $a_1,\ a_2,\ …,\ a_n\ (1≤a_i≤n)$，表示初始的星标数值。

所有测试数据中 $n$ 的总和不超过 $5×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⋅1=2$；

选择 $i=3$ ，并使其右边的所有元素与之相等，则代价为 $1⋅1=1$。

总费用为 $2+1=3$ 。

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