说明

在大法师学院，有一个特殊的传统：每位毕业生都必须完美掌握排序魔法球的仪式。

在一个长长的祭坛上，从左到右放置着 $n$ 个球，每个球都有编号。每个球都有一个给定的强度值，为了成功完成仪式，它们必须按照强度非递减的顺序排列。为了实现这一点，可以交换球，并且一次操作可以交换任意两个球。

然而，位置 $i$ 和 $j$ 之间的魔法流是不稳定的，交换这两个位置上的球需要花费 $(i - j - 2)^2$ 单位的法力值。

当球被排列成正确的顺序时，仪式即视为完成。你需要以一种使得总法力消耗最小化的方式来进行仪式。

你需要回答多个关于进行仪式的独立询问。

输入格式

第一行包含一个整数 $t$ （$1 \le t \le 2 \cdot 10^5$）—— 仪式的数量。

接下来是每个仪式的描述。

每个仪式的第一行包含一个整数 $n$ （$1 \le n \le 2 \cdot 10^5$）—— 球的数量。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ （$0 \le a_i \le 10^9$）—— 每个球的强度值。

保证所有仪式中 $n$ 的总和不超过 $2 \cdot 10^5$。

输出格式

对于每个仪式，输出一个整数 —— 完成仪式所需的最小法力消耗。

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

0
1
2

提示

翻译由 DeepSeek 完成