每个测试时间限制：2 秒
每个测试内存限制：256 兆字节

题目说明

这是该问题的简单版本。两个版本的区别在于，在此版本中 $1 \le n \le 5 \cdot 10^3$，并且你不需要为每个前缀输出答案。只有当你解决了该问题的所有版本时，才能进行 Hack。

Leo 在市中心做程序员，他的爱人在郊区的一所高中教书。每个周末，Leo 都会骑自行车去郊区与爱人共度美好周末。

此刻，Leo 前方的道路上共有 $n$ 名骑行者在骑行。他们从前到后编号为 $1, 2, \dots, n$。初始时，Leo 位于第 $n$ 名骑行者的后面。第 $i$ 名骑行者有一个敏捷值 $a_i$。

Leo 想要骑到第 $1$ 名骑行者前面。Leo 可以无限次地执行以下操作：

• 假设 Leo 前方的第一个骑行者是 $i$，他可以花费 $a_i$ 的成本骑到他前面。这会使他位于第 $i-1$ 名骑行者之后（如果 $i=1$，则表示他已经位于第 $1$ 名骑行者前面）。
• 使用他的超能力，花费 $(j-i)$ 的成本交换 $a_i$ 和 $a_j$（$1 \le i < j \le n$）。

Leo 想知道骑到第 $1$ 名骑行者前面的最小成本。这里你只需要输出针对完整数组 $[a_1, a_2, \dots, a_n]$ 的答案。

输入格式

每个测试包含多个测试用例。
第一行包含一个整数 $t$（$1 \le t \le 10^3$），表示测试用例的数量。
接下来每个测试用例的格式如下：

• 第一行包含一个正整数 $n$（$1 \le n \le 5 \cdot 10^3$），表示骑行者的数量。
• 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^9$）。

数据保证所有测试用例的 $n$ 之和不超过 $5 \cdot 10^3$。

输出格式

对于每个测试用例，输出一个整数，表示 Leo 从第 $n$ 名骑行者后面移动到第 $1$ 名骑行者前面的最小成本。

示例

输入

4
3
1 2 4
4
1 1 1 1
2
1 2
4
4 1 3 2

输出

7
4
3
8

样例解释

第一个测试用例：
一种可能的移动方式如下：

1. Leo 交换 $a_2$（$i=2$）和 $a_3$（$j=3$），数组变为 $[1,4,2]$，花费 $j-i = 3-2 = 1$。
2. Leo 位于第 $3$ 名骑行者后面，移动到第 $2$ 名骑行者后面，花费 $a_3 = 2$。
3. Leo 交换 $a_1$（$i=1$）和 $a_2$（$j=2$），数组变为 $[4,1,2]$，花费 $j-i = 2-1 = 1$。
4. Leo 位于第 $2$ 名骑行者后面，移动到第 $1$ 名骑行者后面，花费 $a_2 = 1$。
5. Leo 交换 $a_1$（$i=1$）和 $a_2$（$j=2$），数组变为 $[1,4,2]$，花费 $j-i = 2-1 = 1$。
6. Leo 移动到第 $1$ 名骑行者前面，花费 $a_1 = 1$。

总成本为 $1+2+1+1+1+1 = 7$。可以证明 $7$ 是最小成本。

第二个测试用例：
为了从第 $n$ 名骑行者后面移动到第 $1$ 名骑行者前面，Leo 不应该交换任何人的敏捷值。总成本为 $1+1+1+1 = 4$。