CF2107F1 Cycling (Easy Version)

> 这是此问题的简单版本，和其他版本的区别是此版本中 $n\le 5000$，且你不需要对每个前缀都求解。 Leo 骑车去见他的女朋友。在 Leo 的前面有 $n$ 名骑手，从前往后排在第 $i$ 名的骑手的灵活度为 $a_i$。 Leo 将要加速超过前面的所有骑手，他可以执行以下两种操作： - 当他在骑手 $i$ 后面，骑手 $i+1$ 前面（或 $i=n$）时，付出 $a_i$ 的代价超过骑手 $i$，之后他将在骑手 $i$ 前面，骑手 $i-1$ 后面（如果 $i>1$）； - 使用他的超级力量交换 $a_i$ 和 $a_j$，代价为 $\vert i-j\vert$。 请你找出超过所有 $n$ 名骑手的最小代价。

多组数据，第一行一个整数 $t(1\le t\le 1000)$，表示数据组数。 对于每组数据，第一行一个整数 $n(1\le n\le 5000)$。\ 第二行 $n$ 个整数 $a_1,a_2,\cdots,a_n(1\le a_i\le 10^9)$。 保证单个测试点中 $\sum n\le 5000$。

对于每组数据，输出一行一个整数，表示答案。

**样例解释** 第一组数据中，一组操作如下所示： - 交换 $a_2$ 和 $a_3$，之后 $a=(1,4,2)$，代价为 $1$； - 超过第 $3$ 名骑手，代价为 $2$； - 交换 $a_1$ 和 $a_2$，$a=(4,1,2)$，代价为 $1$； - 超过第 $2$ 名骑手，代价为 $1$； - 交换 $a_1$ 和 $a_2$，$a=(1,4,2)$，代价为 $1$； - 超过第 $1$ 名骑手，代价为 $1$。 总代价为 $7$。可以证明这是最小的代价。 第二组数据中如果一直执行“超过”操作，花费为 $4$。可以证明这是最小的代价。 By chenxi2009